💬 Discord
Sign In
NeetCode #3LC-242EasyArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#3 · #242 · Valid Anagram(有效的字母异位词)

📌 Problem Statement & Constraints

Given two strings s and t, return true if t is an anagram of s, and false otherwise. Constraints: 1 <= s.length, t.length <= 5 * 10^4; both strings consist of lowercase English letters.

💡 Core Algorithmic Approaches

  1. An anagram must have the same length, so reject immediately when len(s) != len(t).
  2. Because the alphabet is fixed at 26 lowercase letters, a length-26 integer array is a perfect frequency table.
  3. Increment the counter for every character of s, decrement it for every character of t.
  4. If the array is all zeros at the end, the multisets match. Equivalently, use Counter(s) == Counter(t).

💻 Benchmark Python3 Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):           # anagram requires equal length
            return False
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - 97] += 1
        for ch in t:
            cnt[ord(ch) - 97] -= 1
        return all(c == 0 for c in cnt)


# Follow-up with Unicode / arbitrary alphabet: use a hash map instead
class Solution2:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import Counter
        return Counter(s) == Counter(t)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) where n is the string length: two linear passes plus a constant 26-element scan. The Counter variant is also O(n) but with a larger constant.
💾 Space Complexity
O(1) for the fixed 26-slot array -- the alphabet size does not grow with the input. The Counter variant is O(k) in the number of distinct characters.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the length check: it is not strictly required for correctness with the counter approach, but it is a free O(1) early exit and a common interview signal.
  • Sorting both strings: O(n log n) and allocates two new lists. It is a valid answer but the counting approach is strictly better for a fixed alphabet.
  • Assuming lowercase-only when the follow-up asks about Unicode: an array of 26 breaks; switch to Counter or a dict.
  • Comparing set(s) == set(t): sets discard multiplicity, so s = "aab" and t = "abb" would be wrongly accepted.