title: Valid Anagram
slug: valid-anagram
difficulty: easy
leetcode_id: 242
leetcode_url: https://leetcode.com/problems/valid-anagram/
categories:
  - strings
  - hash-tables
  - sorting
patterns:
  - slug: hashing
    is_optimal: true

function_signature: "def is_anagram(s: str, t: str) -> bool:"

test_cases:
  visible:
    - input: { s: "anagram", t: "nagaram" }
      expected: true
    - input: { s: "rat", t: "car" }
      expected: false
  hidden:
    - input: { s: "a", t: "a" }
      expected: true
    - input: { s: "ab", t: "a" }
      expected: false
    - input: { s: "listen", t: "silent" }
      expected: true
    - input: { s: "hello", t: "world" }
      expected: false
    - input: { s: "", t: "" }
      expected: true
    - input: { s: "aaa", t: "aaaa" }
      expected: false
    - input: { s: "aacc", t: "ccac" }
      expected: false

description: |
  Given two strings `s` and `t`, return `true` if `t` is an *anagram* of `s`, and `false` otherwise.

  An **anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

constraints: |
  - `1 <= s.length, t.length <= 5 * 10^4`
  - `s` and `t` consist of lowercase English letters.

examples:
  - input: 's = "anagram", t = "nagaram"'
    output: "true"
    explanation: "Both strings contain exactly the same characters: three 'a's, one 'n', one 'g', one 'r', and one 'm'."
  - input: 's = "rat", t = "car"'
    output: "false"
    explanation: "The strings have different characters: 'rat' has a 't' while 'car' has a 'c'."

explanation:
  intuition: |
    Think of each string as a **bag of letters**. Two words are anagrams if and only if they contain the exact same letters with the exact same frequencies.

    Imagine you have two piles of Scrabble tiles. To check if they're anagrams, you could sort both piles alphabetically and see if they match perfectly. Alternatively, you could count how many of each letter appears in the first pile, then verify the second pile has identical counts.

    The key insight is that **order doesn't matter** — only the character frequencies. This transforms a string comparison problem into a counting problem, which we can solve efficiently with a hash map or a fixed-size array.

  approach: |
    We solve this using a **Character Frequency Count** approach:

    **Step 1: Check lengths**

    - If `s` and `t` have different lengths, they cannot be anagrams — return `false` immediately
    - This is a quick optimisation that avoids unnecessary work

    &nbsp;

    **Step 2: Count character frequencies**

    - Create a frequency array of size 26 (one slot for each lowercase letter)
    - Iterate through both strings simultaneously
    - For each character in `s`, increment its count
    - For each character in `t`, decrement its count
    - This "cancels out" matching characters

    &nbsp;

    **Step 3: Verify all counts are zero**

    - After processing both strings, check if all counts are exactly `0`
    - Any non-zero count means one string has more or fewer of that character
    - Return `true` only if all 26 counts are zero

    &nbsp;

    This approach works because incrementing for `s` and decrementing for `t` means a perfect match leaves every count at zero.

  common_pitfalls:
    - title: Forgetting the Length Check
      description: |
        Strings of different lengths cannot be anagrams. While the counting approach will still produce the correct answer, checking lengths first is an O(1) optimisation that can exit early.

        For example, comparing "abc" to "abcd" would require counting 7 characters before discovering the mismatch. The length check catches this instantly.
      wrong_approach: "Skipping the length comparison"
      correct_approach: "Check if len(s) != len(t) first"

    - title: Using a Dictionary for Lowercase-Only Input
      description: |
        When the problem guarantees lowercase English letters only, using a Python dictionary (hash map) is overkill. A fixed-size array of 26 integers is faster and uses less memory.

        The array approach has O(1) access per character and predictable memory usage. Use `ord(c) - ord('a')` to map characters to indices 0-25.
      wrong_approach: "Using collections.Counter for simple lowercase strings"
      correct_approach: "Use a fixed-size array when character set is known"

    - title: Sorting When Counting Suffices
      description: |
        Sorting both strings and comparing them works correctly, but it's O(n log n) time complexity. The counting approach achieves O(n) time, which matters for large inputs.

        With constraints up to `5 * 10^4` characters, the difference between O(n) and O(n log n) is significant.
      wrong_approach: "sorted(s) == sorted(t)"
      correct_approach: "Count frequencies in O(n) time"

  key_takeaways:
    - "**Character frequency pattern**: Many string problems reduce to counting character occurrences"
    - "**Fixed-size array optimisation**: When the character set is bounded (e.g., 26 lowercase letters), arrays beat hash maps"
    - "**Early exit optimisation**: Simple checks like length comparison can avoid unnecessary computation"
    - "**Related problems**: Group Anagrams, Find All Anagrams in a String, and Permutation in String all use similar counting techniques"

  time_complexity: "O(n). We iterate through both strings once, where `n` is the length of the strings."
  space_complexity: "O(1). We use a fixed-size array of 26 integers, regardless of input size. This is technically O(26) = O(1) constant space."

  pattern_comparison: |
    **Counting Array vs Hash Map vs Sorting: Choose Your Weapon**

    Three valid approaches with different trade-offs:

    | Approach | Time | Space | Best For |
    |----------|------|-------|----------|
    | **Counting Array** | O(n) | O(1) | Fixed character set (a-z, A-Z) |
    | **Hash Map (Counter)** | O(n) | O(k) | Unicode, variable character sets |
    | **Sorting** | O(n log n) | O(n) | Simplest code, small inputs |

    **Why Counting Array wins here:**
    - The problem guarantees lowercase English letters only (26 characters)
    - Array indexing (`ord(c) - ord('a')`) is faster than hash function computation
    - Memory layout is contiguous and cache-friendly
    - True O(1) space since array size is constant

    **When to use Hash Map instead:**
    - Unicode strings with unpredictable character sets
    - When the follow-up asks "What if inputs contain Unicode characters?"
    - When readability matters more than micro-optimisation

    **When Sorting is acceptable:**
    - Quick prototyping or one-off scripts
    - When you need the sorted strings for other purposes
    - For very short strings where the O(n log n) factor is negligible

    **Interview tip**: Start with the array approach for the O(1) space, then mention the Counter approach as a "cleaner but slightly slower alternative."

solutions:
  - approach_name: Character Frequency Count
    is_optimal: true
    code: |
      def is_anagram(s: str, t: str) -> bool:
          # Different lengths can't be anagrams
          if len(s) != len(t):
              return False

          # Fixed-size array for 26 lowercase letters
          count = [0] * 26

          # Increment for s, decrement for t
          for i in range(len(s)):
              count[ord(s[i]) - ord('a')] += 1
              count[ord(t[i]) - ord('a')] -= 1

          # All counts should be zero for anagrams
          return all(c == 0 for c in count)
    explanation: |
      **Time Complexity:** O(n) — Single pass through both strings.

      **Space Complexity:** O(1) — Fixed 26-element array regardless of input size.

      We use the increment/decrement trick: adding for characters in `s` and subtracting for characters in `t`. If they're anagrams, every character "cancels out" to zero.

  - approach_name: Hash Map Counter
    is_optimal: false
    code: |
      from collections import Counter

      def is_anagram(s: str, t: str) -> bool:
          # Counter creates a dictionary of character frequencies
          return Counter(s) == Counter(t)
    explanation: |
      **Time Complexity:** O(n) — Building each Counter takes linear time.

      **Space Complexity:** O(k) — Where k is the number of unique characters (at most 26 for lowercase).

      This approach is more readable and works with any character set (including Unicode). Python's `Counter` class handles the frequency counting automatically. The trade-off is slightly higher memory overhead compared to the array approach.

  - approach_name: Sorting
    is_optimal: false
    code: |
      def is_anagram(s: str, t: str) -> bool:
          # Sort both strings and compare
          return sorted(s) == sorted(t)
    explanation: |
      **Time Complexity:** O(n log n) — Sorting dominates the runtime.

      **Space Complexity:** O(n) — Python's sorted() creates new lists.

      This is the most intuitive approach: if two strings are anagrams, their sorted versions must be identical. While correct, it's slower than counting for large inputs. Useful for understanding the problem but not optimal for interviews.
