Valid Anagram

Problem Description

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An anagram uses all the original letters exactly once, just rearranged.

Examples

Constraints

• 1 ≤ s.length, t.length ≤ 5 * 10⁴
• s and t consist of lowercase English letters.

Two Strings Are Anagrams When Their Character Counts Are Identical

Sorting both strings and comparing them works, but O(n log n) is more than you need. The actual question is simpler: does every character appear the same number of times in both strings? That’s a counting problem, and counting runs in O(n).

Count up for s, count down for t, then check that everything is balanced. Any non-zero count means a mismatch.

Solution 1: Sort and Compare

Sort both strings and check equality. If they’re anagrams, the sorted versions are identical.

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

#include <string>
#include <algorithm>

class Solution {
public:
    bool isAnagram(std::string s, std::string t) {
        if (s.size() != t.size()) return false;
        std::sort(s.begin(), s.end());
        std::sort(t.begin(), t.end());
        return s == t;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). Sorting dominates.
• Space Complexity: O(n) for Java/Python (new arrays/strings), O(1) for C++ (sorts in place).

Where it breaks: if the interviewer asks for O(n) time, this doesn’t qualify. Also, sorting modifies the string, which matters if you can’t mutate the input.

Solution 2: Character Frequency Map

Use a single frequency array of size 26. Increment for each character in s, decrement for each character in t. If every entry is 0 at the end, the strings are anagrams.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            // if this goes below zero, t has a character s doesn't have enough of
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
}

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        # Counter subtraction: if counts match perfectly, result is empty
        return Counter(s) == Counter(t)

#include <string>

class Solution {
public:
    bool isAnagram(std::string s, std::string t) {
        if (s.size() != t.size()) return false;

        int count[26] = {};
        for (char c : s) count[c - 'a']++;
        for (char c : t) {
            // if this goes below zero, t has more of this char than s
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Two linear scans, O(1) per character.
• Space Complexity: O(1). Fixed-size array of 26 entries regardless of input size.

Where it breaks: this only works for lowercase English letters. If the follow-up extends to Unicode, you need a hash map instead of a fixed array. Mention this proactively.

Why Not Use a Hash Map Instead of an Array?

For lowercase ASCII, a 26-element array beats a hash map on constant factors: no hashing overhead, no collision handling, better cache locality. The logic is the same. Use the hash map only when the character set is unbounded (Unicode follow-up).

Common Mistakes

• Not checking lengths first. Two strings of different lengths can never be anagrams. This early return avoids extra work and guards against false positives on the counting approach.
• Using a set instead of a count array. A set tells you which characters appear, not how many times. “aab” and “abb” would both give {a, b} but are not anagrams.
• Forgetting the Unicode follow-up. Interviewers at larger companies frequently ask: “what if the input contains Unicode?” Have the hash map version ready.

Frequently Asked Questions

What if the strings contain Unicode characters? Replace the 26-element array with a hash map keyed by character. The algorithm is identical; just substitute count[c - 'a'] with count.get(c, 0).

Can you solve this without counting characters? Sorting works (O(n log n)), but no O(n) approach avoids some form of counting. There’s no way to verify equal character frequencies faster than counting them.

What does this problem test in interviews? Mostly whether you reach for the right tool: an array for bounded character sets, a map for unbounded ones. The sorting solution works but signals you haven’t thought about complexity.

← All Problems