9. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An anagram uses exactly the same letters as the original, each the same number of times, possibly in a different order.

Example 1

Input: s = "night", t = "thing"
Output: true

Explanation: Both words contain one each of g, h, i, n and t.

Example 2

Input: s = "apple", t = "paper"
Output: false

Explanation: s has two ps and an l; t has two ps and an r.

Example 3

Input: s = "ab", t = "a"
Output: false

Explanation: Strings of different lengths can never be anagrams.

Constraints

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters

Follow-up: What changes if the strings may contain arbitrary Unicode characters instead of just lowercase letters?

💡 Hint 1

If the lengths differ, the answer is immediately false.

💡 Hint 2

Sorting both strings and comparing works in O(n log n). Can you do better by counting?

💡 Hint 3

Keep 26 counters: add one for each letter of s, subtract one for each letter of t, then check that every counter is zero.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Two strings are anagrams exactly when every letter appears the same number of times in both. After checking that the lengths match, keep an array of 26 counters: increment for each character of s and decrement for each character of t. If any counter is non-zero at the end, the letter multisets differ.

Time O(n)Space O(1) (26 counters)

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every((c) => c === 0);
}

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

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit