Valid Anagram | Leetcode 242 | Optimal Hash Map Solution

The Valid Anagram problem asks us to check if two given strings s and t are anagrams of each other.

• An anagram is a word or phrase formed by rearranging the letters of another word.
• Both strings must use the same letters with the same frequency.
• If they are anagrams, return True; otherwise, return False.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings use the same letters: {a, n, g, r, a, m}.

Example 2

Input: s = "rat", t = "car"
Output: false
Explanation: "rat" and "car" do not use the same letters.

Intuition and Approach

To check if two strings are anagrams, we need to verify:

1. Length Check:
   • If s and t are of different lengths, they can’t be anagrams.
2. Character Frequency Count:
   • Use a hash map (dictionary) to count occurrences of each character in s.
   • Traverse through t, and for each character:
     • Check if it exists in the hash map.
     • Decrease its frequency count.
     • If a character is missing or count goes below zero, return False.
3. Final Check:
   • If all counts balance out, then the two strings are anagrams.

This method ensures both efficiency and correctness.

Code Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        chars = {}
        for ch in s:
            chars[ch] = chars.get(ch, 0) + 1
        for ch in t:
            if ch not in chars:
                return False
            else:
                if chars[ch] == 0:
                    return False
                chars[ch] -= 1
        return True

Code Explanation

• Length Check: If lengths differ, return False.
• Counting in s:
  • Each character’s frequency is stored in the dictionary chars.
• Processing t:
  • If ch is not in chars, return False.
  • If count is already zero, return False.
  • Otherwise, decrement the count.
• Return: If we finish processing without conflicts, return True.

Dry Run

Input: s = "anagram", t = "nagaram"

1. Count characters in s: {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}
2. Process characters in t:
   • ‘n’: count goes 1 → 0
   • ‘a’: count goes 3 → 2
   • ‘g’: count goes 1 → 0
   • ‘a’: count goes 2 → 1
   • ‘r’: count goes 1 → 0
   • ‘a’: count goes 1 → 0
   • ‘m’: count goes 1 → 0
3. All counts balanced → return True.

Time and Space Complexity

• Time Complexity:
  • Counting characters in s → O(N)
  • Processing t → O(N)
  • Overall = O(N), where N is the length of the strings.
• Space Complexity:
  • Extra dictionary to store counts → O(K), where K = number of unique characters.

Conclusion

The Valid Anagram problem is solved efficiently using a hash map to count character frequencies.

• Step 1: Compare lengths.
• Step 2: Count characters in s.
• Step 3: Validate against t.
• Step 4: If everything matches, return True.

This approach runs in O(N) and is optimal for both interviews and real-world scenarios.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.