Start learning free

LESSON 224 OF 438 · SORTING

Valid Anagram in Python: O(n log n) by Sorting Both Strings

Practice O(n log n) Read the full explanation

Given two strings s and t, return True if t is an anagram of s, and False otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.


Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= s.length, t.length <= 5 * 104
  • s and t consist of lowercase English letters.

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, "anagram" and "nagaram": what do you notice when you put the letters of each one in alphabetical order?
Now take two strings that are not anagrams, "rat" and "car": 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 "anagram" and of "nagaram" both read "aaagmnr", so the two strings are anagrams.
Sorted, the letters of "rat" read "art" and those of "car" read "acr": 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

    PYTHON · SORTING

    Valid Anagram in Python, explained

    Problem overview

    The method isAnagram receives two strings, s and t, and returns True if t is an anagram of s: the same letters rearranged, each used exactly as many times as before. Otherwise it returns False. Both strings consist of lowercase English letters and each has between 1 and 50,000 characters.

    For s = "anagram" and t = "nagaram" the answer is True, since both strings contain three a, and one each of g, m, n and r. For s = "rat" and t = "car" the answer is False, because t has a c that s lacks.

    Approach: sorting removes the order

    Two strings are anagrams exactly when they contain the same letters with the same counts. The only thing that differs between anagrams is the order of the letters. Sorting removes that difference: sort both strings, and anagrams turn into identical sequences.

    For "anagram" and "nagaram", both sort to a a a g m n r. For "rat" and "car", the sorted versions are a r t and a c r, which differ. So the whole problem reduces to sorting twice and comparing.

    The lesson asks for O(n log n) time and O(n) extra space, which is exactly what two sorts and a comparison cost. Faster solutions exist: counting the letters takes O(n) time. This lesson takes the sorting route.

    Step by step

    1. Sort s. The variable sortedS holds sorted(s). The built-in sorted accepts any iterable, and a string is an iterable of characters, so it returns a new list of the letters in alphabetical order.
    2. Sort t the same way into sortedT. Treating both strings identically is what makes the two results comparable.
    3. Return whether they are equal. The == operator on two lists compares them element by element. Equal lists mean the same letters in the same order, which, after sorting, means the same letters with the same counts. Lists of different lengths are never equal, so no separate length check is needed.

    The solution in Python

    class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        sortedS = sorted(s)
        sortedT = sorted(t)
        return sortedS == sortedT

    Python details worth knowing:

    • sorted() returns a list, not a string. sorted("anagram") is ['a', 'a', 'a', 'g', 'm', 'n', 'r']. Comparing that list with a string never gives True: sorted("anagram") == "aaagmnr" is False. Both sides of the comparison have to be lists, or both strings, for example by wrapping each result in "".join(...).
    • sorted() versus .sort(). Strings have no sort method, because they are immutable. For a list, l.sort() sorts in place and returns None, so writing x = l.sort() leaves x equal to None. sorted() leaves its argument alone and returns a new list.
    • List equality is deep. == compares length first in effect and then each pair of elements, and characters compare by their code, so the result is a plain True or False.

    Complexity

    Time: O(n log n + m log m), where n and m are the lengths of s and t. Each sort costs O(k log k) for a string of length k, and the final comparison costs at most O(n). When the lengths are equal this is O(n log n).

    Space: O(n + m). sorted builds a new list for each string and leaves the originals untouched.

    Edge cases and common mistakes

    • Different lengths. s = "a" and t = "ab" give two lists of different lengths, which are never equal, so the result is False with no extra check.
    • Same letters, different counts. "ab" and "abb" fail on length. For equal lengths, "aab" and "abb" sort to a a b and a b b and compare as different. Checking only that every letter of s appears somewhere in t would wrongly accept such a pair.
    • Identical strings. A string is always an anagram of itself, and the method returns True.
    • Mixing a list and a string. As above, sorted(s) == t is always False, even for real anagrams.
    • Assuming sorting is free. Sorting is the dominant cost, which is why this solution is O(n log n) rather than linear.

    Testing

    • s = "anagram", t = "nagaram" gives True.
    • s = "rat", t = "car" gives False.
    • s = "a", t = "ab" gives False.
    • s = "aab", t = "abb" gives False.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free