Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram uses the exact same characters with the exact same frequencies.

Examples

Example 1:

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

Example 2:

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

Constraints

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters

Follow-up: What if the inputs contain Unicode characters?

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Thinking Process

Two strings are anagrams if and only if they have the same character frequencies. Three ways to check this:

  1. Frequency array – since only 26 lowercase letters, use a fixed-size array. Increment for s, decrement for t. If all counts are zero, it’s an anagram.
  2. Hash map – generalizes to Unicode. Same logic but with a map instead of an array.
  3. Sorting – sort both strings and compare. Simplest but slowest.

The key trick: increment and decrement in the same array. If everything cancels to zero, the frequencies match.

Two pointers 1 3 5 7 9 L R move L/R based on comparison

Approach 1: Frequency Array – O(n) time, O(1) space

The expected optimal solution. Since characters are lowercase letters, a 26-element array suffices.

Input: s = "anagram", t = "nagaram"
Output: True

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: Two strings are anagrams if and only if they have the same character frequencies. Three ways to check this:

How the code works:

  1. Frequency array – since only 26 lowercase letters, use a fixed-size array. Increment for s, decrement for t. If all counts are zero, it’s an anagram.
  2. Hash map – generalizes to Unicode. Same logic but with a map instead of an array.
  3. Sorting – sort both strings and compare. Simplest but slowest.

Walkthrough — input s = "anagram", t = "nagaram", expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Hash Map – O(n) time, O(n) space

Generalizes to Unicode characters. Use a map instead of a fixed array.

Input: s = "rat", t = "car"
Output: False

Time: O(n) Space: O(n) – up to n distinct characters

Approach 3: Sorting – O(n log n)

Sort both strings and compare directly. Simplest to write but slowest.

from collections import Counter


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        base = ord("a")
        for c in s:
            cnt[ord(c) - base] += 1
        for c in t:
            idx = ord(c) - base
            cnt[idx] -= 1
            if cnt[idx] < 0:
                return False
        return True

Time: O(n log n) Space: O(1) (ignoring sort internals)

Comparison

Approach Time Space Unicode?
Frequency Array O(n) O(1) No (26 letters only)
Hash Map O(n) O(n) Yes
Sorting O(n log n) O(1) Yes

Common Mistakes

  • Forgetting the length check – different-length strings can never be anagrams
  • Using two separate arrays/maps instead of one (works but wastes space)
  • Not handling the follow-up: frequency array only works for fixed alphabets

Key Takeaways

  • Frequency counting is the core technique for anagram/permutation problems
  • The ++ / -- in one array trick is reusable: same pattern appears in sliding window permutation checks
  • For small fixed alphabets, arrays beat hash maps in both speed and simplicity

References

Template Reference