242. Valid Anagram

Determining whether two strings are anagrams is a frequently asked problem in technical interviews at companies like Google, Amazon, and Microsoft. This problem tests your understanding of hash maps, character frequency analysis, and optimization techniques that can reduce time complexity from logarithmic to linear.

Problem statement

You are given two strings, str1 and str2. Your task is to determine if str2 is an anagram of str1.

An anagram is formed by rearranging the letters of a word or phrase to create a new word or phrase, using all the original letters exactly once.

Constraints:

• 1 ≤ str1.length, str2.length ≤ 10⁴
• str1 and str2 consist of only lowercase English letters

Examples

Why sorting based approach is impractical

The most straightforward way to verify if two strings are anagrams is to first check if they have the same length. If they don’t, we can immediately return False since anagrams must contain the same number of characters. If the lengths match, we can sort both strings alphabetically and then compare them character by character. If the sorted versions are identical, the strings are anagrams; otherwise, they are not.

This sorting-based solution has a time complexity of O(n log n), where n represents the length of the strings. The bottleneck is the sorting operation, which dominates the runtime. The space complexity is O(1) if we sort in place, or O(n) if the sorting algorithm creates temporary arrays. While this approach works correctly, it performs unnecessary work by fully ordering the characters when we only need to verify that character frequencies match. For large inputs or performance-critical systems, we can do better by eliminating the sorting step entirely.

Optimized approach using frequency counting

Instead of sorting the strings, we can solve this problem in linear time by counting character frequencies. The core insight is that two strings are anagrams if and only if every character appears the same number of times in both strings. We can use a hash map to track these frequencies efficiently.

The beauty of this approach is that it uses the fact that we don’t need the characters to be in any particular order, we only care about how many times each character appears. By incrementing counts for characters in the first string and decrementing counts for characters in the second string, we can quickly verify whether the frequency distributions match.

This method works because we’re essentially creating a frequency signature for the first string, then checking if the second string has the exact same signature. If any character count ends up non-zero after processing both strings, we know the frequencies don’t match and the strings aren’t anagrams. This avoids the O(n log n) cost of sorting while maintaining correctness.

Step-by-step algorithm

1. Check if the lengths of str1 and str2 are different. If they are, immediately return False since anagrams must have equal lengths.
2. Create an empty hash map called table to store character frequencies.
3. Iterate through each character in str1 and increment its count in table. If the character doesn’t exist in the map yet, initialize it with a count of 1.
4. Iterate through each character in str2 and decrement its count in table. If a character from str2 doesn’t exist in table, return False immediately since this character wasn’t in str1.
5. After processing both strings, iterate through all values in table and check if any count is not equal to 0.
6. If any count is non-zero, return False. Otherwise, return True.

1 / 6

Code implementation

def is_anagram(str1, str2):
    # If lengths differ, strings cannot be anagrams
    if len(str1) != len(str2):
        return False
    
    # Hash map to store character frequencies
    table = {}
    
    # Count character frequencies in str1
    for char in str1:
        if char in table:
            table[char] += 1
        else:
            table[char] = 1
    
    # Decrement character frequencies using str2
    for char in str2:
        if char in table:
            table[char] -= 1
        else:
            # Character in str2 not found in str1
            return False
    
    # Verify all counts are zero
    for key in table:
        if table[key] != 0:
            return False
    
    return True


def main():
    str1_list = ["secure", "triangle", "garden", "apple", "notebook"]
    str2_list = ["rescue", "integral", "danger", "pale", "booknet"]
    
    for i in range(len(str1_list)):
        print(i + 1, ".\tstr1: \"", str1_list[i], "\"", sep="")
        print("\tstr2: \"", str2_list[i], "\"", sep="")
        result = is_anagram(str1_list[i], str2_list[i])
        print('\t"', str2_list[i], '" is anagram of "', str1_list[i], '": ', result, sep="")
        print("-" * 75)


if __name__ == '__main__':
    main()

Time complexity

The time complexity of this algorithm is O(n), where n is the length of the input strings. We perform three separate iterations: one to count character frequencies in str1, another to decrement frequencies using str2, and a final pass to verify all counts are zero. Each iteration processes at most n characters, giving us O(n) + O(n) + O(n) = O(n). This is a significant improvement over the sorting-based approach.

Space complexity

The space complexity of this algorithm is O(1) in practice, though technically O(k) where k is the size of the character set. Since the problem constraints specify only lowercase English letters, the hash map will contain at most 26 key-value pairs regardless of input size. This constant upper bound means the space usage doesn’t grow with n, making it effectively constant space.