Problem Explanation

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 another, using all the original letters exactly once.

Example:

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

Output: true

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

Output: false

Approach Discussion

1. Using an Object to Count Characters

• Logic:
  • Use an object (obj) to store the frequency of characters in s.
  • Decrease the frequency for characters in t while traversing.
  • If at any point a character in t doesn’t exist in obj or the frequencies don’t balance to 0, return false.
  • Finally, check if all values in the object are 0.
• Code:

function isAnagram(s, t) {
    if (s.length !== t.length) return false;

    let obj = {};

    // Count frequencies of characters in `s`
    for (let i = 0; i < s.length; i++) {
        obj[s[i]] = (obj[s[i]] || 0) + 1;
    }

    // Decrease frequencies based on characters in `t`
    for (let i = 0; i < t.length; i++) {
        if (!obj[t[i]]) return false; // Character not found or excess in `t`
        obj[t[i]]--;
    }

    // Ensure all frequencies are balanced
    for (let key in obj) {
        if (obj[key] !== 0) return false;
    }

    return true;
}

• Time Complexity: O(N)
  • Traverse both strings once and iterate over the object.
• Space Complexity: O(N)
  • Space is used to store the character frequencies in the object.

2. Using an Array for Counting (Optimized for Lowercase Letters)

• Logic:
  • Use an array of size 26 (for lowercase English letters) to track character frequencies.
  • Increment the frequency for characters in s and decrement for characters in t.
  • At the end, check if all values in the array are 0.
• Code: