Valid Anagram

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.

Example:
Input: s = “anagram”, t = “nagaram”
Output: true

Approach: Hash Map / Frequency Counter

The most efficient way to solve this is to count the occurrences of each character. Since the problem typically limits the characters to lowercase English letters, we can use an array of size 26 or a standard JavaScript object/Hash Map to track frequencies.

1. First, check if the lengths of s and t are different. If they are, they cannot be anagrams, so return false.
2. Initialize a frequency map (or an object) to store character counts.
3. Iterate through both strings simultaneously. Increment the count for the character from s and decrement the count for the character from t.
4. Finally, iterate through the frequency map. If any character count is not exactly 0, it means the strings have different characters or quantities. Return false.
5. If all counts are 0, return true.

Solution

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    
    const count = {};
    
    for (let i = 0; i < s.length; i++) {
        count[s[i]] = (count[s[i]] || 0) + 1;
        count[t[i]] = (count[t[i]] || 0) - 1;
    }
    
    for (let char in count) {
        if (count[char] !== 0) {
            return false;
        }
    }
    
    return true;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the strings. We iterate through the strings once, which takes $O(n)$ time. The final loop through the hash map takes $O(1)$ time because there are at most 26 unique characters.
• Space Complexity: $O(1)$. The size of the hash map is bounded by the number of unique characters in the alphabet (e.g., 26 lowercase English letters), so it requires constant extra space regardless of the input size.