Topic: Learning notes

LeetCode 242: Valid Anagram in TypeScript, From Sorting to Character Counts

Compare sorting, Map-based frequency differences, and a fixed-size count array for Valid Anagram, including correctness, invariants, and complexity.

This note keeps my own sorting solution and my Map-based improvement, then adds a later 26-slot count array based on the problem constraint. All three versions check the string lengths first. They differ in how much extra data they keep to compare character frequencies.

Problem

Original problem: LeetCode 242: Valid Anagram

Given two strings s and t made of lowercase English letters, return true when t is an anagram of s, otherwise return false. The strings are anagrams only when they contain the same characters with the same frequencies.

Brute force searches for each character again

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

  const remaining = t.split("");

  for (const char of s) {
    const index = remaining.indexOf(char);

    if (index === -1) return false;

    remaining.splice(index, 1);
  }

  return true;
}

For each character in s, this code searches the remaining characters and removes one match. Both indexOf() and splice() can visit a linear number of elements, so the total time is O(n²). remaining copies t, which costs O(n) extra space.

My first solution: sorting

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

  const sortedS = s.split("").sort().join("");
  const sortedT = t.split("").sort().join("");

  return sortedS === sortedT;
}

Different lengths cannot have the same total character count, so the early return is valid. When the lengths match, sorting puts equal characters into the same order. Equal sorted strings therefore have the same character set and count for every character.

This was my first correct solution. In interview discussions, comparison sort is normally described as O(n log n), so sorting both strings is still O(n log n). split() and join() create new values, making the auxiliary space O(n). JavaScript does not require Array.prototype.sort() to use one fixed algorithm or complexity. The O(n log n) statement is the usual interview model, not a language-specification guarantee. MDN’s sort reference explicitly notes that the real complexity depends on the implementation.

My Map-based improvement

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

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

  for (let index = 0; index < s.length; index += 1) {
    const left = s[index];
    const right = t[index];

    counts.set(left, (counts.get(left) ?? 0) + 1);
    counts.set(right, (counts.get(right) ?? 0) - 1);
  }

  return [...counts.values()].every((count) => count === 0);
}

This was my improvement over sorting. It adds one for a character from s and subtracts one for the character at the same index in t. If every Map value is zero after the scan, the two strings have cancelled out every character count.

There is no need to spread the strings into sArr and tArr first. Strings support indexed character access, so those two array copies add work without helping the algorithm. In interview analysis, Map reads and writes are expected O(1), making total time expected O(n). The Map stores at most k distinct characters, so auxiliary space is O(k) and O(n) in the worst case. It is not O(1). MDN’s Map reference requires average access to be sublinear, without requiring one particular implementation.

A later 26-slot count array based on the constraint

The two previous versions are my own solutions. The original problem limits the input to 26 lowercase English letters, so this later improvement can use a fixed-size count array instead of a Map.

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

  const counts = new Array<number>(26).fill(0);
  const firstLowercaseCode = "a".charCodeAt(0);

  for (let index = 0; index < s.length; index += 1) {
    counts[s.charCodeAt(index) - firstLowercaseCode] += 1;
    counts[t.charCodeAt(index) - firstLowercaseCode] -= 1;
  }

  return counts.every((count) => count === 0);
}

Each letter has one fixed index, such as a at 0 and z at 25. The scan increments one count and decrements one count. The array always has 26 entries, independent of the input length, so the algorithm takes O(n) time and O(1) auxiliary space.

This is the better choice for the exact problem constraint. If the character range is not fixed, such as the Unicode follow-up, use a Map instead.

Why the counting solution is correct

After processing index, counts[char] equals the number of times char appears in s[0..index] minus the number of times it appears in t[0..index].

At the end, all counts are zero exactly when every character has the same frequency in both strings. A non-zero count means at least one character has a different frequency, so the answer must be false.

Complexity comparison

Minimal verification

import assert from "node:assert/strict";

assert.strictEqual(isAnagram("anagram", "nagaram"), true);
assert.strictEqual(isAnagram("aasdqqweqw", "qwerw"), false);
assert.strictEqual(isAnagram("cat", "tar"), false);
assert.strictEqual(isAnagram("aa", "a"), false);

The second case checks the early return for different lengths. The third has equal lengths with different character frequencies, so it confirms that the code does more than compare length. Node’s assert documentation documents assert.strictEqual().

Common mistakes

• Calling sorting O(n²). Use O(n log n) in a normal interview answer, while noting that JavaScript does not guarantee one fixed sort() complexity.
• Calling the Map solution O(n log n). Under the hash-lookup model, it is expected O(n).
• Calling the Map storage O(1). The number of distinct characters can grow with the input.
• Checking only the lengths. Equal length says nothing about per-character counts.
• Applying the 26-slot array to Unicode input. That optimization only fits the lowercase-English constraint.

Transferable idea

When two collections need to match by per-item frequency, keep the difference in counts instead of building two complete statistics and comparing them afterward. The same pattern appears in string grouping, sliding windows, and frequency-counting problems.

References

• LeetCode 242: Valid Anagram: original problem, examples, and lowercase-English constraint.
• MDN: Array.prototype.sort(): in-place sorting and implementation-dependent complexity.
• MDN: Map: key-value semantics and average access requirement.
• Node.js: assert.strictEqual(): strict equality for minimal assertions.