Valid Anagram easy

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 1:

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

Example 2:

Input: s = "rat", t = "car" Output: false

Steps:

1. Handle edge cases: Check if the lengths of s and t are different. If they are, they cannot be anagrams, so return false.

2. Character Counting: Create two maps (or objects in JavaScript/TypeScript) to store the frequency of each character in s and t. Iterate through each string and increment the count for each character in its respective map.

3. Comparison: Compare the two maps. If they have the same keys and the values (counts) for each key are identical, then the strings are anagrams, and we return true. Otherwise, return false.

Explanation:

The solution leverages the fact that anagrams have the same characters with the same frequencies. By counting the character frequencies, we can efficiently determine if two strings are anagrams without needing to generate all possible permutations of one string. Using maps provides a convenient way to store and compare character frequencies.

Code:

function isAnagram(s: string, t: string): boolean {
    // Edge case: different lengths means not anagrams
    if (s.length !== t.length) {
        return false;
    }

    // Character frequency maps
    const sMap: { [char: string]: number } = {};
    const tMap: { [char: string]: number } = {};

    // Count character frequencies
    for (let i = 0; i < s.length; i++) {
        sMap[s[i]] = (sMap[s[i]] || 0) + 1;
        tMap[t[i]] = (tMap[t[i]] || 0) + 1;
    }

    // Compare character frequencies
    for (const char in sMap) {
        if (sMap[char] !== tMap[char]) {
            return false;
        }
    }

    return true; 
}


//Example usage
console.log(isAnagram("anagram", "nagaram")); //true
console.log(isAnagram("rat", "car")); //false
console.log(isAnagram("", "")); //true - handles empty strings
console.log(isAnagram("a", "aa")); //false - handles different lengths

Complexity:

• Time Complexity: O(n), where n is the length of the input strings. We iterate through each string once to count character frequencies and then iterate through the map once for comparison.
• Space Complexity: O(1) In the worst case, the space used by the maps will be bounded by the number of unique characters in the alphabet (26 for lowercase English letters), making it constant space. If we consider a larger character set, the space complexity would become O(k) where k is the size of the character set.