Skip to content
LEETFLIX

Valid Anagram

EasyHashingStringSorting
Solve on LeetCode

Easy · count characters. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 242. Valid Anagram. The copyrighted prompt is on LeetCode. This page is a working count characters for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

s =
anagram
t =
nagaram

Output

true

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Frequency map

Count letters in s, subtract letters in t. A leftover or a missing letter means not an anagram.

Two strings are anagrams iff they have the same multiset of characters. One map is enough: +1 for s, −1 for t.

Algorithm

  1. If lengths differ, return false.
  2. Increment counts for s, decrement for t.
  3. Every count must land on zero.
Time
O(n)
Space
O(σ)
Solution.py
class Solution:    def isAnagram(self, s: str, t: str) -> bool:        if len(s) != len(t):            return False        count: dict[str, int] = {}        for ch in s:            count[ch] = count.get(ch, 0) + 1        for ch in t:            count[ch] = count.get(ch, 0) - 1            if count[ch] < 0:                return False        return True
Watch this run

03

Interactive walkthrough

Playing “Frequency map”. Edit the input, hit Run, then scrub.

Approach: Frequency map

Loading animation…