Start learning free

LESSON 306 OF 671 · SORTING

Valid Anagram

Practice O(n log n)

You get two strings, s and t.

Return true if t has the same letters as s, in any order. Otherwise, return false.

Each letter must appear the same number of times in both. Then t is called an anagram of s. For example, "thing" is an anagram of "night".


Example 1:

Input: s = "stressed", t = "desserts"
Output: true
Explanation: Both words have the same letters:
one d, one r and one t,
two e's,
three s's.

Example 2:

Input: s = "letter", t = "settle"
Output: false
Explanation: Both words have 6 letters.
But "letter" has an r where "settle" has an s.

Example 3:

Input: s = "loot", t = "lot"
Output: false
Explanation: Both words use l, o and t.
But "loot" has two o's and "lot" has only one.

 

Constraints:

  • Each string has 1 to 50,000 characters.
  • The two strings can have different lengths.
  • Both strings use only lowercase English letters, a to z.

Note:

For this lesson, your algorithm should run in O(n log n) time and use O(n) extra space for the sorted copies of the two strings.
(There are faster solutions which we will discuss in future lessons)


Hints:

Sorting the characters of the two strings might be helpful here. Take two strings that are anagrams, "stressed" and "desserts": what do you notice when you put the letters of each one in alphabetical order?
Now take two strings that are not anagrams, "letter" and "settle": what do you notice when you sort their letters?

Two strings are anagrams if and only if their sorted letters are exactly the same.
Sorted, the letters of "stressed" and of "desserts" both read "deerssst", so the two strings are anagrams.
Sorted, the letters of "letter" read "eelrtt" and those of "settle" read "eelstt": they differ, so the two strings are not anagrams.
And this is the solution: sort the characters of both strings and compare the results. Return true if they are equal and false otherwise.
(Counting how many times each letter appears in each string, and comparing the counts, works too: that is one of the faster solutions.)

Sorting the string s takes O(n log n) where n is the length of s.
Sorting the string t takes O(m log m) where m is the length of t.
Checking if the sorted strings are equal takes O(n).
So the final time complexity is O(n log n + m log m).
The sorted copies of s and t take O(n + m) extra space.
STEP 1 OF 3
    Ctrl + Enter to check