Valid Anagram

EasyString Hash Table Sorting

In a letter-shuffle game, a player is shown the word s and must reply with a word t that uses all of its letters in a new order. The reply is accepted only if t is an anagram of s: every letter occurs in t exactly as many times as it occurs in s, no more and no fewer.

Given s and t, return true if the reply is accepted and false otherwise. Replying with the original word unchanged also counts as an anagram.

Example 1

Input: s = "below", t = "elbow"
Output: true

Explanation: Both words use one each of b, e, l, o and w.

Example 2

Input: s = "sleep", t = "spell"
Output: false

Explanation: sleep has two es and one l, while spell has one e and two ls.

Example 3

Input: s = "note", t = "tones"
Output: false

Explanation: t has an extra s, and words of different lengths can never be anagrams.

Constraints

s and t are each between 1 and 50,000 characters long.
Both strings use lowercase English letters only.

Follow-up: The 26-slot counter relies on a tiny alphabet. What would you count with if the words could contain any Unicode character, and why do characters outside the Basic Multilingual Plane need extra care in JavaScript strings?

💡 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