Valid Anagram

Q: What is the time complexity of Valid Anagram?

Counting letters takes O(n) time and O(1) extra space, because the counter array has 26 entries no matter how long the strings are. Sorting both strings takes O(n log n) time and usually O(n) space for the sorted copies.

Q: Is it better to sort or to count when checking for an anagram?

Counting is faster in theory, O(n) against O(n log n) , and it can stop as soon as one letter is overused. Sorting is shorter to write and works for any alphabet without changes. In an interview, mention the sort first and then improve it to counting.

EasyHashing Sorting

+10

Two strings are anagrams when one is a rearrangement of the other: they use the same letters, and each letter the same number of times. You get two strings s and t made of lowercase English letters. Return true if t is an anagram of s, and false otherwise.

Function

isAnagram(s: string, t: string) → boolean

sstring: the first string, lowercase letters
tstring: the string to test against s
Returnsboolean: true if t uses exactly the letters of s, each the same number of times

Constraints

1 ≤ s.length, t.length ≤ 2 × 10⁴
s and t contain only lowercase English letters (a to z).
The two lengths may differ.

Examples

Input: s = "listen"t = "silent"
Output: true
Explanation: Both words hold one e, i, l, n, s and t, so silent is listen with its letters moved around.

Input: s = "aabb"t = "abbb"
Output: false
Explanation: The lengths match and both use only a and b, but aabb has two as and abbb has one. The counts have to match, not only the letters.

Input: s = "cat"t = "cast"
Output: false
Explanation: cast has four letters and cat has three, so no rearrangement of cat can spell it.

+19 hidden tests on Submit

Follow-up

What if the strings could hold any Unicode character instead of a to z? How would you change the counting?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

An anagram keeps the letter counts and throws away the order. So you need a summary of each string that forgets where the letters were but remembers how many of each there are. Sorting builds that summary in O(n log n); a table of 26 counters builds it in one pass.

Sort both strings

Intuition

Sorting puts the letters of a string in alphabetical order and erases where each one started. listen sorts to eilnst, and so does silent, so they are anagrams. aabb stays aabb and abbb stays abbb; they differ at index 1, so they are not.

The test works in both directions. If t is a rearrangement of s, the two hold the same letters the same number of times, so sorting produces the same sequence. If the sorted sequences are equal, t uses exactly the letters of s.

Compare the lengths first: strings of different lengths are never anagrams, and you skip both sorts. Sorting costs O(n log n) time, and most languages sort a copy of the characters, which is O(n) extra space. At n = 2 × 10^4 this is fast, but the counting approach does less work.

Algorithm

If the lengths of s and t differ, return false.
Copy the characters of each string into an array.
Sort both arrays.
Return true if the sorted arrays are equal, element by element.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Count each letter

Intuition

Only 26 letters can appear, so keep one counter per letter in an array of 26, with index 0 for a and index 25 for z. The index of a letter is its character code minus the code of a. Walk s and add 1 to each letter's counter, then walk t and subtract 1.

You can stop early: a counter below 0 means t has used that letter more often than s has it. For aabb and abbb, after s the counters read a: 2 and b: 2. Then t takes b three times, the third one drives b to -1, and you return false on the spot.

Why is "no counter went negative" enough? The lengths are equal, so the counters add up to 0 after both walks. If none is negative, a positive one would have nothing to balance it, so every counter is 0 and the counts match. This is why the length check is required, not only a shortcut.

Each string is read once, which is O(n) time. The array always holds 26 numbers, whatever the length, so the extra space is O(1).

Algorithm

If the lengths of s and t differ, return false.
Create an array of 26 zeros.
For each letter of s, add 1 to its counter.
For each letter of t, subtract 1 from its counter; if it drops below 0, return false.
Return true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Pitfalls and edge cases

Most wrong answers come from checking which letters appear instead of how many times, or from dropping the length check.

Comparing the sets of letters. aabb and abbb both use exactly a and b, yet they are not anagrams.
Checking that every letter of t occurs somewhere in s without crossing it off. aab and abb pass that test in both directions.
Skipping the length check in the counting version. With s = ab and t = a, no counter goes below 0, so the code would wrongly return true.
Indexing the counter array with the raw character code. a is 97, far past the end of an array of 26; subtract the code of a first. In Lua and R add 1, since their arrays start at index 1.

Frequently asked questions4

What is the time complexity of Valid Anagram?

Counting letters takes O(n) time and O(1) extra space, because the counter array has 26 entries no matter how long the strings are. Sorting both strings takes O(n log n) time and usually O(n) space for the sorted copies.

Is it better to sort or to count when checking for an anagram?

Counting is faster in theory, O(n) against O(n log n), and it can stop as soon as one letter is overused. Sorting is shorter to write and works for any alphabet without changes. In an interview, mention the sort first and then improve it to counting.

How do you check anagrams that contain Unicode characters?

Replace the array of 26 counters with a hash map from character to count. Add 1 for each character of s, subtract 1 for each character of t, and check that every count ends at 0. Read the strings by whole characters, not bytes, so that a character stored in several bytes counts once.

Why use one counter array instead of two?

Two arrays, one per string, work too: count each string, then compare the arrays. One array that goes up for s and down for t uses half the memory and lets you return false the moment a counter goes negative, without a final comparison loop.

Python

def isAnagram(s, t):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "listen"
t = "silent"

Expected

true