192. Valid Anagram

Two strings are anagrams exactly when they have identical letter counts. Tally the counts of s, then subtract using t; if any count goes negative or lengths differ, they aren't anagrams.

Idea

An anagram uses the same multiset of letters. So s and t are anagrams if and only if every character appears the same number of times in both. Counting is O(n) and beats sorting's O(n log n).

Algorithm

1. If len(s) != len(t), they can't be anagrams — return false.
2. Build a frequency map counts from s (counts[c] += 1).
3. Walk t: for each character c, if counts[c] is already 0 (or missing) then t has a letter s doesn't have enough of → return false; otherwise counts[c] -= 1.
4. If we finish without a shortfall, return true.

Worked example: s = "anagram", t = "nagaram"

Counts of s: a:3, n:1, g:1, r:1, m:1. Subtracting each letter of nagaram: n→a:3,n:0; a→a:2; g→g:0; a→a:1; r→r:0; a→a:0; m→m:0. Every count lands exactly at 0 with no shortfall → true.

Contrast s = "rat", t = "car": counts of rat = r:1,a:1,t:1. Subtracting car: c isn't in the map → return false.

Complexity

• Time: O(n) — two linear passes.
• Space: O(1) — at most 26 lowercase letters.

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