Start learning free

LESSON 228 OF 442 · SORTING

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

    SCALA · SORTING

    Valid Anagram in Scala, explained

    Problem overview

    The method isAnagram(s: String, t: String): Boolean returns true when t can be made by rearranging the letters of s, using every letter exactly once, and false otherwise. Both strings are lowercase and have between 1 and 50,000 characters.

    With s = "anagram" and t = "nagaram" the answer is true: both strings have three a, and one each of g, m, n and r. With s = "rat" and t = "car" the answer is false, because t has a c that s lacks.

    The lesson asks for O(n log n) time and O(n) extra space. Faster ways to do this exist, and they come in later lessons. This one uses sorting.

    Approach: sorting removes the order

    Two strings are anagrams exactly when they hold the same letters the same number of times. The only thing that differs is the order, and sorting takes the order away. Sort the letters of "anagram" and you get "aaagmnr". Sort the letters of "nagaram" and you get "aaagmnr" too. Equal sorted strings mean equal letter counts, and the other way round.

    For "rat" and "car" the sorted strings are "art" and "acr". They differ at the second character, so the strings are not anagrams.

    The plan is therefore three lines: sort s, sort t, compare the results.

    Different lengths need no special case. A string of length 3 can never equal a string of length 4, so if s = "ab" and t = "abb", the comparison is false by itself.

    Step by step

    1. Sort s. val sortedS = s.sorted keeps the letters of s in alphabetical order. On a String, sorted returns a new String, so sortedS is a string, ready to compare.
    2. Sort t the same way. Both words go through the same treatment, which is what makes the comparison fair.
    3. Compare. sortedS == sortedT is true if and only if the two sorted strings have the same characters in the same places. The expression is the method's result.

    The solution in Scala

    class Solution {
    def isAnagram(s: String, t: String): Boolean = {
        val sortedS = s.sorted
        val sortedT = t.sorted
        return sortedS == sortedT
    }
}

    The Scala details worth a closer look:

    • sorted returns a new value. Strings are immutable in Scala, so s.sorted leaves s unchanged and gives back a new string. After val sortedS = s.sorted, both s and sortedS are usable. Those two copies are the O(n) extra space.
    • Sorting a string gives a string. A String is treated as a sequence of Char values. Calling sorted on it orders them by character code and builds a String again. For lowercase letters, character code order is alphabetical order.
    • == compares contents. In Scala, == on strings compares their characters, not their identity, so two different string objects with the same letters are equal. Unlike Java, there is no need for equals.
    • val versus var. The sorted strings are never reassigned, so val is the right choice.
    • The return keyword. Scala methods return the value of their last expression, so sortedS == sortedT alone would do. The explicit return behaves the same here, because it is not inside a loop or a function literal.

    Complexity

    Time: O(n log n + m log m), where n and m are the lengths of s and t. Each sort takes time proportional to its length times the logarithm of it, and the final comparison walks the strings once, which is O(n) and doesn't change the total. If the lengths differ, the comparison stops at once. With n the larger of the two lengths, this is O(n log n).

    Space: O(n + m). The two sorted copies are new strings with as many characters as the originals.

    Counting how many times each letter appears, in an array of 26 integers, avoids sorting and gives O(n) time. This lesson keeps to sorting because it needs the fewest lines and the fewest places for a mistake.

    Edge cases and common mistakes

    • Different lengths. "ab" and "abb" are not anagrams. Sorting gives "ab" and "abb", which are unequal, so the comparison returns false with no extra check.
    • Same letters, different counts. "aab" and "abb" have the same length and the same set of letters, yet they are not anagrams. Sorting gives "aab" and "abb", which differ. Checking only that each letter of t appears somewhere in s would wrongly accept this pair.
    • Identical strings. A string is an anagram of itself, so "abc" and "abc" give true.
    • A single letter. "a" and "b" give false, and "a" and "a" give true.
    • Expecting s to be sorted afterwards. s.sorted doesn't change s. The sorted version is only in the new value, so you have to use that value.

    Testing

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