Coding Interview Questions | Valid Anagram

December 16th, 2023

Introduction:

This summary will talk about my solution to the valid anagram problem as seen on leetcode here.

Solution:

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

  const sCharCountMap = new Map<string, number>();
  const tCharCountMap = new Map<string, number>();

  for (let sIdx = 0; sIdx < s.length; sIdx++) {
    const sChar = s[sIdx];

    const currentCharCount = sCharCountMap.get(sChar);

    if (currentCharCount === undefined) {
      sCharCountMap.set(sChar, 1);
      continue;
    }

    sCharCountMap.set(sChar, currentCharCount + 1);
  }

  for (let tIdx = 0; tIdx < t.length; tIdx++) {
    const tChar = t[tIdx];

    const sCharCount = sCharCountMap.get(tChar);
    const tCharCount = tCharCountMap.get(tChar);

    // s string did not contain character,
    // not an anagram
    if (!sCharCount) {
      return false;
    }

    // t character has not been seen yet,
    // but does exist in s
    if (!tCharCount) {
      tCharCountMap.set(tChar, 1);
      continue;
    }

    // t character has been seen
    // too many times relative to
    // time seen in s
    if (tCharCount >= sCharCount) {
      return false;
    }

    tCharCountMap.set(tChar, tCharCount + 1);
  }

  return true;
}

Summary:

The solution above determines whether two input strings, s and t, are anagrams by comparing their lengths and employing character count maps. The algorithm initializes a Map object, sCharCountMap, to store the character counts of string s. It then iterates through the characters of string t, comparing character counts between the two strings. If a character in t is not present in s or appears more times in t than in s, the algorithm returns false. The early exit optimization checks for different string lengths, given two words cannot be an anagram if they are of differing lengths.

The solution has a time and space complexity of O(n), where n is the length of the strings, by iterating through each character only once and utilizing Map objects for storage.