Valid Anagram — Counting Characters in O(n)

Valid Anagram is officially an Easy problem, but it is a perfect early stop on the path to mastering string and hashing patterns. Interviewers love it because it tests whether you reach for sorting reflexively or whether you can spot the linear counting solution.

The Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a rearrangement of the same characters, so the two strings must contain the same multiset of letters.

Example 1:

• Input: s = "anagram", t = "nagaram"
• Output: true

Example 2:

• Input: s = "rat", t = "car"
• Output: false

The classic constraint says the strings contain only lowercase English letters, but the follow-up asks how you would handle Unicode characters.

Intuition

The easiest correct solution is to sort both strings and compare them. Two anagrams produce the same sorted sequence. That is O(n log n) time and O(n) space for the sorted copies. It is short and readable, which makes it a fine baseline, but we can do better.

If the alphabet is fixed and small (26 lowercase letters), counting characters is linear and constant-space. We walk s and increment the bucket for each character, then walk t and decrement. If any bucket drops below zero, t contains a letter that s does not have enough of, and we can stop early. If we finish without that happening and the lengths match, every bucket is zero.

For the Unicode follow-up we swap the fixed array for a hash map (or a Counter), still linear time but allocating only the characters that actually appear.

Explanation with Example

Take s = "anagram" and t = "nagaram". After scanning s, the counts array holds three a’s, one n, one g, one r, and one m. Scanning t, the first n drops n to zero, the next a drops a from three to two, then g, a, r, a, m. Every decrement keeps the bucket non-negative, and the final array is all zeros, so we return true.

Now take s = "rat" and t = "car". After s we have one r, one a, one t. Walking t, the first c decrements c from zero to negative one, and we return false immediately. The early termination is a small but useful optimization.

index :  a  b  c  d  e  f  g  h  i  ... m  n  ... r  ...
after s: [3, 0, 0, 0, 0, 0, 1, 0, 0, ... 1, 1, ... 1, ...]
after t: [0, 0, 0, 0, 0, 0, 0, 0, 0, ... 0, 0, ... 0, ...]

every bucket back to 0  ->  return True

scan s:    r:1  a:1  t:1     (others 0)

scan t:    c -> counts[c] = 0 - 1 = -1
                               |
                               v
                        bucket < 0 -> return False

Code

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

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

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        int counts[26] = {0};
        for (char c : s) counts[c - 'a']++;
        for (char c : t) {
            if (--counts[c - 'a'] < 0) return false;
        }
        return true;
    }
};

Edge Cases

• Different lengths: handled by the length check up front. Without it you would still need to compare totals at the end.
• Empty strings: two empty strings are anagrams by definition, and the loops do nothing, so we return true.
• Case sensitivity: the problem treats A and a as different. If a follow-up changes that, normalize with s.lower() before counting.
• Whitespace and punctuation: the standard problem assumes none, but real anagram puzzles often ignore them. Strip them out before counting.
• Unicode: a fixed array of 26 will not work. Use a hash map or Counter.

Complexity Analysis

Both optimal versions run in O(n) time, where n is the length of either string. The array version uses O(1) extra space because the array is always size 26. The hash map variant uses O(k) extra space, where k is the number of distinct characters. The sorting baseline is O(n log n) time and O(n) space. If you are new to these notations, our refresher on Big O notation walks through the reasoning.

How to Explain It in an Interview

• Restate the problem and confirm the alphabet: lowercase English only, or full Unicode.
• Mention sorting as the obvious baseline at O(n log n).
• Pivot to counting: walk s, increment buckets, walk t, decrement, and check for any negative.
• Justify the O(1) space claim by pointing to the fixed 26-letter alphabet.
• Offer the hash map variant as your answer to the Unicode follow-up.

This sequence shows that you can produce a working solution quickly and then refine it without being prompted.

Related Problems

• Group Anagrams, which extends this counting idea across many strings.
• Ransom Note, which is the same character-count check in disguise.
• Find All Anagrams in a String, which combines this with a sliding window.

For more context on the underlying tools, revisit strings introduction and operations and hashing and hash maps.

Wrap up

Valid Anagram is a tiny problem with a big lesson: when the alphabet is small, fixed-size counting beats sorting every time. The two-line sorted comparison is a fine first answer, but moving to a linear count and explaining why it is constant space is what turns a working solution into a strong interview signal.