19. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of a different word, using all the original letters exactly once.

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

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

Problem Breakdown:

1. First, check if the lengths are different. If so, they cannot be anagrams.

• if len(s) != len(t):
      return False

2. Create a frequency counter (hash map) to count character occurrences in the first string.

• count = {}
  for c in s:
      count[c] = count.get(c, 0) + 1

3. Iterate through the second string, decrementing counts. If a character is missing or count goes below zero, it is not an anagram.

• for c in t:
      if c not in count or count[c] == 0:
          return False
      count[c] -= 1

4. If we process all characters without issues, the strings are anagrams.

• return True

Summary:

Count character frequencies in the first string using a hash map, then verify the second string has the same frequencies. Since we only deal with lowercase English letters, space is O(26) = O(1).

Time and Space Complexity:

Time Complexity: O(n) - we iterate through both strings once.

Space Complexity: O(1) - the counter uses at most 26 entries for lowercase English letters.

Python Solution:

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        if c not in count or count[c] == 0:
            return False
        count[c] -= 1
    return True

JavaScript Solution:

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    const count = {};
    for (const c of s) {
        count[c] = (count[c] || 0) + 1;
    }
    for (const c of t) {
        if (!count[c]) return false;
        count[c]--;
    }
    return true;
};

Java Solution:

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0) return false;
        }
        return true;
    }
}