Valid Anagram in Python – Optimal HashMap Approach Explained

Problem Overview

An anagram is formed when two strings contain the same characters with the same frequency, but possibly in a different order. The task is to determine whether two given strings are valid anagrams of each other.

Key Observation

Since character order does not matter in an anagram, comparing strings position by position is ineffective. What actually matters is the frequency of each character in both strings.

Optimal Approach Using HashMaps

We use two hashmaps (dictionaries) to count the frequency of characters in both strings. If both maps are identical, the strings are anagrams.

• Traverse the first string and count character frequencies
• Traverse the second string and count character frequencies
• Compare both frequency maps

Python Code Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_map = {}
        t_map = {}

        for ch in s:
            s_map[ch] = s_map.get(ch, 0) + 1

        for ch in t:
            t_map[ch] = t_map.get(ch, 0) + 1

        return s_map == t_map

Full source code on GitHub: Valid Anagram – Python Solution

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the strings.

The space complexity is O(1) because the problem restricts input to lowercase English letters, so the hashmap size is bounded by a constant (26 characters).

Alternative Approaches

One alternative approach is sorting both strings and comparing them, but that results in O(n log n) time complexity. Another optimal variation is using a single hashmap or Python’s built-in Counter class.

Conclusion

Using hashmaps to compare character frequencies is the most efficient and interview-friendly solution to the Valid Anagram problem. This approach clearly demonstrates how constraints impact space complexity and helps build strong pattern recognition for similar problems.