Valid Anagram

easyArrays & Hashing79 stepsJava · Python · C++

Two strings are anagrams when they use exactly the same letters the same number of times. Count letters of s up and letters of t down in one array of 26 counters; they are anagrams only if every counter ends at zero.

▶ Watch the animated trace

Traced input: s = "anagram", t = "nagaram" → true. Original problem: neetcode.io/problems/is-anagram

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(1)

Best case is a length mismatch. The 26 counters are constant space.

Key idea

Different lengths can never be anagrams, so check that first.
One pass: count[s[i]]++ and count[t[i]]-- together.
If any counter is non-zero at the end, some letter is over- or under-used.
An int[26] beats a HashMap for lowercase letters: faster and simpler.

Common mistakes

Forgetting the length check, then reading past the end of the shorter string.
c - 'a' breaks on uppercase or Unicode; use a HashMap<Character, Integer> for the follow-up.
Sorting both strings works but is O(n log n).

Solution

Java

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int k = 0; k < 26; k++) {
        if (count[k] != 0) {
            return false;
        }
    }
    return true;
}

Python

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord('a')] += 1
        count[ord(b) - ord('a')] -= 1
    for c in count:
        if c != 0:
            return False
    return True

C++

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) {
        return false;
    }
    int count[26] = {0};
    for (size_t i = 0; i < s.size(); i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }
    for (int k = 0; k < 26; k++) {
        if (count[k] != 0) {
            return false;
        }
    }
    return true;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Different lengths Rejected before any counting.	`s = "ab", t = "abc"`	`false`
Same letters, different counts 'a' ends at +1 and 'c' at -1.	`s = "aacc", t = "ccac"`	`false`
Empty strings No letters, all counters zero.	`s = "", t = ""`	`true`
Identical strings Every letter cancels at the same index.	`s = "rat", t = "rat"`	`true`
Uppercase letters `'A' - 'a'` is -32. Only lowercase English letters are allowed by the problem; for Unicode use a map.	`s = "Ab", t = "bA"`	`throws ArrayIndexOutOfBoundsException`