Valid Anagram

The problem

You are given two strings, text and target_text. Return true if target_text is an anagram of text, and false otherwise.

An anagram uses exactly the same letters, each one the same number of times, just in a different order. So “listen” and “silent” are anagrams, but “seen” and “send” are not.

Example 1

Input: text = "night", target_text = "thing"

Output: true

Both words use g, h, i, n and t once each.

text

n0i1g2h3t4

target_text

t0h1i2n3g4

Example 2

Input: text = "seen", target_text = "send"

Output: false

text has two e’s and no d. target_text has one e and a d.

Example 3

Input: text = "ab", target_text = "abc"

Output: false

The words have different lengths, so they cannot hold the same letters.

Constraints

• 1 ≤ text.length, target_text.length ≤ 50,000 (below, n is the length of text)
• text and target_text hold only lowercase English letters, a to z.

Clarifying questions

Which letters can appear?

Only a to z, lowercase. That means 26 counters are enough.

Does a word count as its own anagram?

Yes. "abc" and "abc" give true. The order does not have to change.

Can the lengths differ?

Yes. Then the answer is false right away, before any other work.

What if the input could be any Unicode text?

Then 26 counters are not enough. Use a hash map from character to count instead. The idea stays the same.

Spot the pattern

The order of the letters does not matter. Only how many times each letter appears matters. When a problem only cares about counts, count them: a small table of counters, or a hash map, replaces any search. That is the hashing pattern.

Solutions

Sort bothO(n log n)Count lettersO(n)

Show all

This problem has two approaches. Pairing each letter by searching the other word works too, but it is slower and teaches nothing new.

Sort both O(n log n)

The idea

Sorting puts letters in a fixed order. Two anagrams hold the same letters, so after sorting they become the same string. Two words that are not anagrams differ somewhere, so their sorted forms differ too.

So check the lengths, sort both words and compare them letter by letter. It is short and clearly correct. The cost is the sort.

Walkthrough

text

n0i1g2h3t4

target_text

t0h1i2n3g4

1. if len(text) != len(target_text):
2. return False
3. sorted_text = sorted(text)
4. sorted_target = sorted(target_text)
5. for i in range(len(text)):
6. if sorted_text[i] != sorted_target[i]:
7. return False
8. return True

Both words have 5 letters, so they might be anagrams. Go on.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort both words: anagrams sort into the same string.
    // Sorting costs O(n log n) time and the sorted copies take O(n) memory.
    public boolean isAnagram(String text, String targetText) {
        // Different lengths can never hold the same letters.
        if (text.length() != targetText.length()) return false;
        char[] sortedText = text.toCharArray();
        char[] sortedTarget = targetText.toCharArray();
        Arrays.sort(sortedText);
        Arrays.sort(sortedTarget);
        // Compares the two arrays letter by letter.
        return Arrays.equals(sortedText, sortedTarget);
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Three lines do the work. Each sort is one line, but a good sort needs about n × log₂ n steps for n letters. The compare inside the loop costs 1 step per run. Here n is the length of the words (they are equal by then).

   1. if len(text) != len(target_text):
   2. return False
   3. sorted_text = sorted(text)
   4. sorted_target = sorted(target_text)
   5. for i in range(len(text)):
   6. if sorted_text[i] != sorted_target[i]:
   7. return False
   8. return True

2. 2 Count the runs on Example 1

   Example 1 has 5 letters in each word. Each sort takes about 5 × log₂ 5 ≈ 5 × 2.3 ≈ 12 steps. The compare loop then runs 5 times, once per position.

   part	sort text	sort target_text	compare
   steps on Example 1	about 5 × log₂ 5 ≈ 12	about 5 × log₂ 5 ≈ 12	5

3. 3 Write the count for any n

   Two sorts and one compare loop:

   n log n + n log n + n = 2 n log n + n

   Check it with Example 1: about 12 + 12 + 5 = 29 steps.

4. 4 Keep only the part that grows fastest

   • Drop the + n. log n keeps growing, so n log n always ends up bigger than n. The sorts are the biggest part.
   • Drop the 2. Doing the sort twice doubles the work, but it does not change how fast the work grows.

   What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   Strings cannot be sorted in place in most languages, so the code makes sorted copies sorted_text and sorted_target. Each holds n letters, so the space is O(n). The loop index i adds 1 more.

   sorted_text (n letters)sorted_target (n letters)i

Count letters O(n)

The idea

Keep one counter per letter, all starting at 0. Walk text and add 1 for each letter. Then walk target_text and take 1 for each letter.

If a counter ever goes below 0, then target_text uses that letter more often than text does. Stop and return false. If we finish, every counter must be exactly 0. Here is why: both words have the same length, so we added and took away the same total. No counter is below 0, so none can be above 0 either.

Why it is correct: two words are anagrams exactly when every letter count matches, and the counters measure the difference in every count at once.

Walkthrough

text

n0i1g2h3t4

target_text

t0h1i2n3g4

letter	g	h	i	n	t
count	0	0	0	0	0

1. if len(text) != len(target_text): return False
2. count = [0] * 26
3. for letter in text:
4. count[letter] += 1
5. for letter in target_text:
6. count[letter] -= 1
7. if count[letter] < 0:
8. return False
9. return True

Same length, so go on. Start one counter per letter at 0. Only the letters that appear are shown here.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count letters: add 1 for each letter of text, take 1 for each letter of targetText.
    // Two passes, so O(n) time. Only 26 counters, so O(1) memory.
    public boolean isAnagram(String text, String targetText) {
        // Different lengths can never hold the same letters.
        if (text.length() != targetText.length()) return false;
        int[] count = new int[26];
        for (char letter : text.toCharArray()) count[letter - 'a']++;
        for (char letter : targetText.toCharArray()) {
            count[letter - 'a']--;
            // targetText uses this letter more often than text does.
            if (count[letter - 'a'] < 0) return false;
        }
        // Same length and nothing went below 0, so every counter is 0.
        return true;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines change one counter and check it. Finding a letter’s counter is a direct jump to slot letter − 'a', with no search. So each run of either loop is 1 step. There are two loops, one after the other, not one inside the other.

   1. if len(text) != len(target_text): return False
   2. count = [0] * 26
   3. for letter in text:
   4. count[letter] += 1
   5. for letter in target_text:
   6. count[letter] -= 1
   7. if count[letter] < 0:
   8. return False
   9. return True

2. 2 Count the runs on Example 1

   Example 1 has 5 letters in each word. The first loop runs 5 times, once per letter of “night”. The second loop runs 5 times, once per letter of “thing”.

   5 + 5 = 10 runs.

   loop	letters	runs
   over text	night	5
   over target_text	thing	5

   total

   5 + 5 = 10

3. 3 Write the count for any n

   Each loop walks one word of length n, one after the other:

   n + n = 2n

   Check it with Example 1: 2 × 5 = 10.

4. 4 Keep only the part that grows fastest

   Drop the 2. Two passes instead of one double the work, but when n doubles, 2n still only doubles. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The counters are an array of 26 numbers, one per letter. That is 26 for a 5-letter word or for a 50,000-letter word. It does not grow with n, so the space is O(1).

   count (26 numbers)letter

Common mistake

Skipping the length check

The early exit inside the second loop only catches letters that target_text has too many of. Without the length check, text = "ab" and target_text = "a" would pass, because no counter goes below 0. Check the lengths first, or check that every counter is 0 at the end.

Tested at the limits

2,000 random word pairs of 1 to 7 letters from a, b and c. Half are real anagrams, and many others are one letter or one count off. The sort both and the count letters gave the same answer every time.

Largest inputs	Result
50,000 letters in each word (the most allowed), a true anagram, so both words are read to the end. Count letters.	0.01 s, and about 0.001 MB of extra memory: just the 26 counts.
50,000 letters in each word. Sort both.	0.01 s, and about 1 MB of extra memory: two sorted copies of 50,000 letters.