Start learning free

LESSON 228 OF 442 · SORTING

Valid Anagram in TypeScript: 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

    TYPESCRIPT · SORTING

    Valid Anagram in TypeScript, explained

    Problem overview

    The method isAnagram receives two strings, s and t, and returns true when t can be formed by rearranging all the letters of s, using each letter exactly as many times as it appears. Both strings are non-empty and use lowercase English letters.

    For s = "anagram" and t = "nagaram" the answer is true: both strings contain three as, 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.

    This lesson's budget is O(n log n) time and O(n) extra space for sorted copies of the two strings. There are faster solutions, but they are not this lesson's subject.

    Approach: sorting removes the order

    Anagrams contain the same letters and differ only in their order. Sorting is a way of throwing the order away: once the letters of each string are in alphabetical order, two strings with the same letters turn into the very same string.

    Here is the idea on the examples:

    "anagram" sorted: aaagmnr
"nagaram" sorted: aaagmnr   (equal, so anagrams)

"rat" sorted: art
"car" sorted: acr           (different, so not anagrams)

    Two strings are anagrams exactly when their sorted versions are equal, so the whole solution is "sort both, then compare". Strings of different lengths can never be equal after sorting, so that case needs no special handling.

    Step by step

    1. Sort the letters of s into sortedS. A TypeScript string has no sort method, because strings are immutable. The recipe has three parts: split("") makes an array of one-letter strings, sort() orders that array, and join("") glues the letters back into a string.
    2. Do the same for t to get sortedT. Both strings get identical treatment, so the results can be compared directly.
    3. Return sortedS === sortedT. The join("") in the earlier steps is what makes this comparison valid: strings are compared by content.

    The solution in TypeScript

    class Solution {
    isAnagram(s: string, t: string): boolean {
        const sortedS = s.split("").sort().join("");
        const sortedT = t.split("").sort().join("");
        return sortedS === sortedT;
    }
}

    The TypeScript details worth a closer look:

    • Why split and join. sort() is an array method. "anagram".split("") gives ["a", "n", "a", "g", "r", "a", "m"], and join("") reverses the conversion after sorting.
    • sort() with no comparator. By default it sorts by converting elements to strings and comparing their UTF-16 code units. For single lowercase letters that is exactly alphabetical order. It would be wrong for numbers: [10, 9, 1].sort() gives [1, 10, 9]. For this lesson no comparator is needed.
    • sort() changes the array in place. It also returns the same array. Here that is harmless, because the array from split is a temporary copy, and s itself is never modified.
    • Comparing arrays with === doesn't work. On arrays it asks whether they are the same object, not whether their contents match, so ["a", "b"] === ["a", "b"] is false. For two array literals tsc reports "This condition will always return 'false' since JavaScript compares objects by reference, not value." Joining the letters into strings first is what lets === compare contents.

    Complexity

    Let n be the length of s and m the length of t.

    Time: O(n log n + m log m). Splitting and joining are linear. Sorting costs O(n log n) for s and O(m log m) for t, and comparing the results is linear. When the lengths are equal, which they must be for an anagram, this is O(n log n).

    Space: O(n + m). The arrays of letters and the sorted strings are copies of the input.

    Edge cases and common mistakes

    • Different lengths. "ab" and "a" give false automatically, since the sorted strings have different lengths.
    • Same letters, different counts. "aab" and "abb" have the same set of letters but not the same counts. Their sorted strings, aab and abb, differ, so the answer is false. A check that only asks whether each letter of t appears in s would wrongly accept them.
    • Identical strings. A word is an anagram of itself, so "abc" and "abc" give true.
    • Skipping join. Comparing the two sorted arrays with === returns false even for real anagrams, because they are different array objects.
    • Calling sort on a string. s.sort() doesn't exist, because sort belongs to arrays. The compiler reports it, and at run time it would throw a TypeError.

    Testing

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