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, so the counts differ.

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

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 a string's letters in alphabetical order and erases where each one started. listen and silent both sort to eilnst; aabb and abbb stay as they are and differ at index 1. Two strings hold the same letters the same number of times exactly when their sorted forms are equal.

Compare the lengths first and skip both sorts when they differ. Sorting costs O(n log n) time and, in most languages, O(n) space for the copy of the characters. At n = 2 × 10^4 that is fast, but counting 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, indexed by the character code minus the code of a. Walk s adding 1 to each letter's counter, then walk t subtracting 1.

A counter below 0 means t uses that letter more often than s, so you can stop there. For aabb and abbb, the counters read a: 2, b: 2 after s; the third b of t drives b to -1, and you return false.

If no counter goes negative, the counts match. The lengths are equal, so the counters sum to 0 after both walks; with none negative, a positive one would have nothing to balance it, so all are 0. That is why the length check is part of the proof and not a shortcut.

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

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

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 wrongly returns 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, and in Lua and R add 1, since their arrays start at 1.

Frequently asked questions3

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.

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.

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

Test #1

Test #2

Test #3

Arguments

s = "listen"
t = "silent"

Expected Output

true