Start learning free

LESSON 224 OF 438 · SORTING

Valid Anagram in JavaScript: O(n log n) by Sorting

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

    JAVASCRIPT · SORTING

    Valid Anagram in JavaScript, explained

    Problem overview

    The method isAnagram(s, t) receives two strings of lowercase letters and returns true when t is an anagram of s: the same letters, each used exactly as many times, in any order. Otherwise it returns false.

    With s = "anagram" and t = "nagaram", both words contain three a, one g, one m, one n and one r, so the answer is true. With s = "rat" and t = "car", the letters t and c don't match, so the answer is false. Each string has between 1 and 50,000 letters, and the two lengths can differ.

    This lesson asks for O(n log n) time and O(n) extra space, and notes that faster solutions exist and come later.

    Approach: sort both words, then compare

    The obvious difficulty is that anagrams list the same letters in different orders. Sorting removes the order. If both words are put in alphabetical order, two anagrams turn into the very same string, and two words that are not anagrams stay different.

    "anagram" sorted: "aaagmnr"
"nagaram" sorted: "aaagmnr"   same, so an anagram

"rat" sorted: "art"
"car" sorted: "acr"           different, so not an anagram

    The statement is exact about why this works: two strings are anagrams if and only if their sorted versions are equal. If the letters and their counts are the same, sorting puts them in the same order. If a letter count differs, the sorted strings differ somewhere, whatever the sort did.

    Strings of different lengths need no special case. A shorter sorted string can't equal a longer one, so the comparison returns false by itself.

    Step by step

    1. Sort the letters of s into a string named sortedS, declared with let. A string has no sort method of its own, so the code does three things in a chain: split('') turns the string into 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 and call the result sortedT. Treating both words the same way makes their sorted forms directly comparable.
    3. Return sortedS === sortedT. The result of the comparison is already a boolean, so the method returns it directly instead of using an if.

    The solution in JavaScript

    var algorithms = require('algorithms')
class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {boolean}
     */
    isAnagram(s, t) {
        let sortedS = s.split('').sort().join('');
        let sortedT = t.split('').sort().join('');
        return sortedS === sortedT;
    }
}

    The first line belongs to the lesson's starter code: it loads a helper library that this solution never uses. The work happens in the three lines of isAnagram. Some JavaScript details worth a closer look:

    • Why the array must be joined back. === on two arrays asks whether they are the very same array in memory, not whether they hold the same letters. [1, 2] === [1, 2] is false. Two strings are compared letter by letter, and "abc" === "abc" is true. That is why the code joins the sorted letters into strings before comparing.
    • sort() with no comparator compares as text. It converts each element to a string and orders by UTF-16 code units. That is a problem for numbers: [10, 9, 1].sort() gives [1, 10, 9]. For single lowercase letters, text order is exactly alphabetical order, so no comparator is needed here.
    • sort() changes the array it is called on and returns the same array. That is harmless here, because split('') made a fresh array that nothing else uses. The original strings are never modified, because strings are immutable.
    • split('') with an empty separator splits between every character, so "rat".split('') is ['r', 'a', 't'].
    • let versus const. The variables are never reassigned, so const would also work. The lesson uses let, and both behave the same here.

    Complexity

    Time: O(n log n + m log m), where n and m are the lengths of s and t. Sorting s costs O(n log n) and sorting t costs O(m log m). Splitting and joining are O(n) and O(m), and the final string comparison is at most as long as the shorter string, so these are smaller than the sorts. When the two strings have the same length, this is O(n log n).

    Space: O(n + m). The method builds an array of letters and a sorted string for each input, so the extra memory grows with the lengths of the two strings.

    A faster method counts the letters instead of sorting them, which takes O(n) time. It needs a table of counts, and that is a different lesson.

    Edge cases and common mistakes

    • Different lengths. "ab" and "abc" sort to "ab" and "abc", which are not equal, so the method returns false with no extra check.
    • Repeated letters. "aab" and "abb" have the same set of letters but different counts. Sorted, they are "aab" and "abb", so the result is false. Comparing sets of letters would wrongly say true.
    • Identical words. A word is an anagram of itself, so isAnagram("a", "a") is true.
    • Comparing arrays with ===. If the code left out join(''), the method would return false for every input, even for two equal words, because two different arrays are never ===.
    • Sorting only one of the strings. Sorting s and comparing it with the unsorted t only works when t happens to be in order already.
    • Calling sort on a string. Strings have no such method, so s.sort() throws a TypeError. The conversion to an array comes first.

    Testing

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