Problem statement

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

An anagram uses exactly the same letters with exactly the same multiplicities, rearranged.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Example 3

Input: s = "aacc", t = "ccac"
Output: false
Explanation: Same letters, but the counts differ.

Constraints

• 1 <= s.length, t.length <= 40
• s and t consist of lowercase English letters.

Follow-up: What if the inputs contained Unicode characters instead of just 26 letters?

Hints for Valid Anagram

1. Hint 1

   Different lengths can never be anagrams — check that first and return early.

2. Hint 2

   Count each of the 26 letters in s, then decrement while scanning t.

3. Hint 3

   The moment a count drops below zero, t has a letter s cannot supply.

How to solve Valid Anagram

Two strings are anagrams exactly when every letter occurs the same number of times in each. Count the letters of s, then let t consume them.

Approach

1. Return false if the lengths differ.
2. Increment a 26-slot count for each letter of s.
3. Decrement for each letter of t; the moment a count goes negative, return false.
4. Return true.

Why it works

With equal lengths, if no count goes negative then t never uses a letter more often than s supplies it, and since the totals match no letter can be under-used either — the multisets are identical.

Complexity

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

Pitfalls

• Sorting both strings and comparing is O(n log n); correct but slower.
• For Unicode inputs replace the fixed array with a hash map.

Reference solution

Python

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for ch in s:
        count[ord(ch) - 97] += 1
    for ch in t:
        idx = ord(ch) - 97
        count[idx] -= 1
        if count[idx] < 0:
            return False
    return True

Java

public static 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']++;
    for (int i = 0; i < t.length(); i++) {
        int idx = t.charAt(i) - 'a';
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
}

C++

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};
    for (char ch : s) count[ch - 'a']++;
    for (char ch : t) {
        int idx = ch - 'a';
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
}

JavaScript

var isAnagram = function(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]++;
    for (let i = 0; i < t.length; i++) {
        const idx = t.charCodeAt(i) - 97;
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy