Valid Anagram

By /

Problem Statement

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, typically using all the original letters exactly once.

The term Valid Anagram refers to the condition where two strings are anagrams of each other.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain the same characters with the same frequencies.

Example 2:

Input: s = "rat", t = "car"
Output: false
Explanation: Different characters present.

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? How would you adapt your solution?

Approach

Initial Thoughts

Two strings are anagrams if they contain exactly the same characters with the same frequencies. We need to verify that every character in s appears in t with identical count, and vice versa.

Strategy

Approach 1 (Sorting): Sort both strings and compare them. If they’re anagrams, sorted versions will be identical.

Approach 2 (Hash Map – Optimal): Count character frequencies in both strings using hash maps and compare the counts.

Approach 3 (Single Hash Map): Count frequencies in s, then decrement counts while iterating through t.

Key Insights

  • Different lengths → automatically not anagrams (quick reject)
  • Anagrams have identical character frequency distributions
  • Sorting changes time complexity to O(n log n)
  • Hash map approach achieves O(n) with O(1) space (only 26 lowercase letters)
  • Can use array of size 26 instead of hash map for fixed alphabet
  • Single pass with counting is more efficient than creating two separate counts

Algorithm Steps

Hash Map Approach:

  1. Quick check: If lengths differ, return false
  2. Create a hash map (or array of size 26) for character counts
  3. First pass: Iterate through s, increment count for each character
  4. Second pass: Iterate through t, decrement count for each character
  5. Validation: Check if all counts are zero
    • If any count is non-zero, return false
    • If all counts are zero, return true

Sorting Approach (Alternative):

  1. If lengths differ, return false
  2. Sort both strings
  3. Compare sorted strings for equality

Complexity Analysis

Hash Map Approach:

Time Complexity: O(n) – Two passes through strings of length n (one for s, one for t)

Space Complexity: O(1) – Using array of size 26 for lowercase English letters (constant space). If using hash map, it’s still O(1) since at most 26 unique characters.

Sorting Approach:

Time Complexity: O(n log n) – Dominated by sorting operation

Space Complexity: O(1) or O(n) depending on sorting algorithm and language

Code

Solution 1: Two Hash Maps (Your Solution – Clean & Optimal)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Quick reject if lengths differ
        if len(s) != len(t):
            return False
        
        # Create separate hashmaps for both strings
        s_hashmap = {}
        t_hashmap = {}
        
        # Build both hashmaps simultaneously in one pass
        for i in range(len(s)):
            s_hashmap[s[i]] = s_hashmap.get(s[i], 0) + 1
            t_hashmap[t[i]] = t_hashmap.get(t[i], 0) + 1
        
        # Compare the two hashmaps
        return s_hashmap == t_hashmap

Solution 2: Using Counter (Pythonic)

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Solution 3: Sorting Approach

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)

Solution 4: Single Hash Map (Space Optimized)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = {}
        
        # Increment for s, decrement for t
        for i in range(len(s)):
            count[s[i]] = count.get(s[i], 0) + 1
            count[t[i]] = count.get(t[i], 0) - 1
        
        # Check if all counts are zero
        return all(val == 0 for val in count.values())

Code Walkthrough

Two Hash Maps Solution (Your Solution):

Line 3-4: Quick optimization – if lengths differ, strings can’t be anagrams

  • Saves time by avoiding unnecessary hashmap construction

Line 7-8: Initialize two empty hashmaps

  • s_hashmap will store character frequencies for string s
  • t_hashmap will store character frequencies for string t

Line 11: Single loop through both strings simultaneously

  • More efficient than two separate loops
  • Uses index i to access characters from both strings at the same position

Line 12: Build frequency map for string s

  • s_hashmap.get(s[i], 0) returns current count or 0 if character not yet seen
  • Increment the count by 1

Line 13: Build frequency map for string t in the same iteration

  • Same logic as line 12 but for string t
  • This parallel construction is efficient and clean

Line 16: Compare the two hashmaps directly

  • Python allows direct dictionary comparison with ==
  • Returns True if both hashmaps have identical key-value pairs
  • Returns False if any character has different frequency

Why this approach is excellent:

  • Clean and readable code
  • Single pass through strings (optimal)
  • Direct hashmap comparison is elegant
  • No need for complex validation logic

Alternative Approaches:

Single Hash Map (Solution 4):

  • Uses one hashmap, incrementing for s and decrementing for t
  • Slightly more space-efficient (one hashmap vs two)
  • Needs extra validation at the end (all(val == 0 for val in count.values()))

Counter (Solution 2):

  • Most Pythonic and concise
  • Essentially does the same thing as your solution under the hood
  • Good for interviews to show Python knowledge

Edge Cases to Consider

  1. Different lengths: s = "a", t = "ab" → false
  2. Empty strings: s = "", t = "" → true (both empty)
  3. Single character – same: s = "a", t = "a" → true
  4. Single character – different: s = "a", t = "b" → false
  5. Same characters, different frequency: s = "aa", t = "ab" → false
  6. All same character: s = "aaaa", t = "aaaa" → true
  7. Long strings: Maximum length 50,000
  8. One character difference: s = "abc", t = "abd" → false
  9. Perfect anagrams: s = "listen", t = "silent" → true

Similar Problems

  • LC 242: Valid Anagram (this problem)
  • LC 49: Group Anagrams
  • LC 438: Find All Anagrams in a String
  • LC 567: Permutation in String
  • LC 383: Ransom Note
  • LC 791: Custom Sort String
  • LC 1347: Minimum Number of Steps to Make Two Strings Anagram
  • LC 2273: Find Resultant Array After Removing Anagrams

Personal Notes

  • This is a fundamental string problem that teaches character frequency counting
  • Your solution (two hashmaps) is excellent because:
    • Very clean and readable
    • Single pass through both strings (optimal)
    • Direct dictionary comparison is elegant and Pythonic
    • Easy to understand and explain in interviews
  • Three main approaches to know:
    1. Two hash maps: Clean, readable, O(n) time – your approach
    2. Single hash map with increment/decrement: Slightly more space-efficient
    3. Sorting: Simple but O(n log n)
  • Interview tip: Your solution is perfect to present first
    • Shows understanding of hashmaps
    • Clean implementation
    • Easy to explain
    • Then mention Counter as a Pythonic alternative
  • For the follow-up (Unicode): Your hashmap approach handles any characters automatically
    • No changes needed for Unicode support
    • Array approach only works for fixed, small alphabets
  • Length check at the start is crucial optimization (fails fast)
  • Why two hashmaps vs one:
    • Two hashmaps: Simpler logic, direct comparison
    • One hashmap: Saves a bit of space, but needs validation loop
    • Both are O(n) time and O(1) space (at most 26 unique lowercase letters)
  • Direct dictionary comparison with == is a Python feature not all languages have
  • The .get(key, default) pattern is cleaner than checking if key in dict
  • Common mistake: Forgetting the length check at the beginning
  • This pattern (character frequency) appears in many string problems
  • Building both hashmaps in the same loop is more efficient than separate loops

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top