LeetCode 242 · Easy · Arrays & Hashing

Valid Anagram

Given two strings s and t, return true if t uses exactly the same letters as s, the same number of times, in any order.

O(n)time
O(1)space
26counters

letters a–z only, 1–20 each · uppercase is lowercased

s
t

count 26 slots · slot = c − 'a' · one block = +1

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;}
pass
—
i
—
c
—
slot
—
count[slot]
—

Why it works

  1. Anagram means same letters, same counts. Order does not matter.
  2. Sort both and compare: correct, but O(n log n).
  3. Count instead: +1 for each letter of s, −1 for each letter of t. Anagram only if every counter ends at 0. One pass each, O(n).
  4. Only 26 lowercase letters, so the array never grows with input: O(1) extra space.
  5. Why a negative count is enough: with equal lengths the counters always sum to 0. If none goes below 0, none can stay above 0 either. So the first negative means false, and reaching the end means true.
  6. Unicode follow-up: letters are no longer 26, so use a HashMap<Integer, Integer> keyed by code point (String.codePoints()), since a Java char is only one UTF-16 unit.