Skip to main content

🟩 Valid Anagram (#242)

🔗 Problem Link​

📋 Problem Statement​

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

💡 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.

🔑 Key Insights & Approach​

Core Observation: Two strings are anagrams if they contain exactly the same characters with the same frequencies. The order doesn't matter, only the counts.

Why Hash Table/Sorting?

  • Hash Table: Count character frequencies in O(n) time
    • Build frequency map for both strings and compare
    • Or use Counter for one-liner solution
  • Sorting: Sort both strings and compare in O(n log n) time
    • Anagrams become identical when sorted: "anagram" → "aaagmnr"
    • Simple but slower than hash table approach

Two Main Approaches:

  1. Sorting: sorted(s) == sorted(t) - Simple one-liner, O(n log n)
  2. Hash Table/Counter: Count character frequencies, O(n) - Optimal

When to Use Each:

  • Sorting: Quick to implement, good for small strings or when code simplicity matters
  • Hash Table: Better time complexity, preferred for large strings or when performance is critical

Pattern Recognition: This is the "Character Frequency Comparison" pattern - when comparing strings based on their character composition, use sorting for simplicity or hash tables for optimal performance.

Follow-up Consideration: What if the strings contain Unicode characters? The hash table approach works naturally, but you'd need to ensure proper character counting.

🐍 Solution: Python​

Approach 1: Using Sorting​

Time Complexity: O(n log n) | Space Complexity: O(1)

def is_anagram(s, t):
    return sorted(s) == sorted(t)

Approach 2: Using Hash Table​

Time Complexity: O(n) | Space Complexity: O(n)

def is_anagram(s, t):
    return Counter(s) == Counter(t)

🔵 Solution: Golang​

Approach 1: Sorting​

Time Complexity: O(n log n) | Space Complexity: O(1)

func isAnagram(s, t string) bool {
    return sorted(s) == sorted(t)
}

Approach 2: Hash Table​

Time Complexity: O(n) | Space Complexity: O(n)

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    countS, countT := make(map[rune]int), make(map[rune]int)
    for i, ch := range s {
        countS[ch]++
        countT[rune(t[i])]++
    }

    for k, v := range countS {
        if countT[k] != v {
            return false
        }
    }
    return true
}

📚 References​