Valid Anagram

Difficulty: Easy

Problem

Two strings s and t are given. Return true if t can be built by rearranging the letters of s, using the same letters with the same counts, and false otherwise.

Example

Input: s = "triangle", t = "integral"
Output: true
Explanation: Both words use the letters a, e, g, i, l, n, r, t exactly once each, so one is a rearrangement of the other.

Brute-force approach

Sort both strings and compare character by character. If sorted strings are identical, they are anagrams.

Steps

  1. Check if lengths are equal (if not, return false)
  2. Sort string s alphabetically
  3. Sort string t alphabetically
  4. Compare sorted strings character by character
  5. If all characters match, they are anagrams

Time complexity: O(n log n) · Space complexity: O(n)

Trade-offs

  • Sorting takes O(n log n) time - not optimal
  • Need extra space O(n) for sorted arrays
  • We can do better with counting approach

Optimal approach

Key insight: Instead of a hash map, use a fixed array of size 26 (for 'a' to 'z'). This gives O(1) space since the size is constant!

Use a fixed-size array of 26 elements (one for each lowercase letter). Increment for characters in s, decrement for characters in t. If all values are zero at the end, they are anagrams.

Steps

  1. Check if lengths are equal
  2. Create array of 26 zeros
  3. For each index: increment count for s[i], decrement for t[i]
  4. Check if all counts are zero

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function isAnagram(s, t):
    if length of s != length of t:
        return false
    
    create count array of size 26, all zeros
    
    for i from 0 to length of s:
        increment count[s[i] - 'a']
        decrement count[t[i] - 'a']
    
    for each value in count:
        if value != 0:
            return false
    
    return true

Hints

  • Use an array of 26 elements for 26 lowercase letters
  • Increment for s, decrement for t in one pass
  • Check if all counts are zero

Complexity questions

Time complexity of sorting both strings?

O(n log n). Sorting dominates: O(n log n) for sorting + O(n) for comparison = O(n log n)

Time complexity of 26-element count array approach?

O(n). One pass through both strings O(n), plus checking 26 elements O(1) = O(n)

Space complexity of 26-element count array?

O(1). Always exactly 26 slots regardless of input size. Fixed size = O(1) constant space!

Why do we say O(1) instead of O(26) for space?

Constants are dropped in Big-O notation. 26 is a constant that doesn't depend on input size n. In Big-O, constants are dropped, so O(26) = O(1).

Check your understanding of Valid Anagram

What is an anagram?

Two words formed by rearranging the same letters. An anagram is a word formed by rearranging all letters of another word. They must use the exact same characters.

Are 'listen' and 'silent' anagrams?

Yes, they use the same letters rearranged. 'listen' and 'silent' both contain: l, i, s, t, e, n - making them anagrams.

Are 'rat' and 'car' anagrams?

No. 'rat' has letters r, a, t while 'car' has c, a, r. The letters don't match (t vs c), so they are NOT anagrams.

Related problems

Keep practising