Start learning free

LESSON 228 OF 442 · SORTING

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

    KOTLIN · SORTING

    Valid Anagram in Kotlin, explained

    Problem overview

    isAnagram(s, t) takes two strings of lowercase letters and returns a Boolean: true when t can be formed by rearranging the letters of s, using every letter exactly once, and false otherwise.

    For s = "anagram" and t = "nagaram" the answer is true: both words are made of three a, one g, one m, one n and one r. For s = "rat" and t = "car" the answer is false, since t has a c that s lacks. Each string has between 1 and 50,000 characters.

    This lesson sets a budget of O(n log n) time and O(n) extra space for the sorted copies, which suits a sorting solution. Faster ways exist and come in later lessons.

    Approach: sort both strings and compare

    Two strings are anagrams exactly when they contain the same letters the same number of times. They differ only in the order of those letters. Sorting removes the order: after sorting, every anagram of a word turns into the same sequence.

    For "anagram" and "nagaram", both sort to aaagmnr, so the sorted forms are equal. For "rat" and "car", the sorted forms are art and acr, which differ at the second letter, so the strings are not anagrams.

    That is the whole algorithm: sort s, sort t, and test the two results for equality. A pair with different lengths needs no special case, because two sequences of different lengths are never equal.

    The alternative idea is to count the letters of each string and compare the counts. That runs in linear time and is the subject of a later lesson. Sorting is simpler to write and a good first version.

    Step by step

    1. Sort s. s.toCharArray() turns the string into a CharArray, and sorted() returns a new list with those characters in ascending order. The original string is untouched. The result goes into sortedS.
    2. Sort t. The same two calls give sortedT. Both strings get identical treatment, so their sorted forms can be compared directly.
    3. Compare. sortedS == sortedT is true when the two lists have the same items in the same order, and that expression is the function's result.

    The solution in Kotlin

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

    Kotlin details worth a look:

    • sorted() returns a List. On a CharArray it doesn't sort in place. It builds a new List<Char>, so "anagram".toCharArray().sorted() is the list [a, a, a, g, m, n, r]. The in-place version is called sort().
    • == on lists compares contents. In Kotlin == calls equals, and for lists that compares item by item. That is exactly what this solution needs.
    • == on arrays does not. Two CharArray values holding the same letters are not equal under ==: for val x = "ab".toCharArray() and val y = "ab".toCharArray(), x == y is false, because arrays compare by reference. x.contentEquals(y) is true. This is the reason the solution compares the lists returned by sorted() rather than sorted arrays.
    • Equivalent forms. s.toList().sorted() gives the same list, because toList() on a string also produces its characters.

    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 equality check is linear. When the lengths are equal, this is O(n log n).

    Space: O(n + m). The function holds two sorted lists, one entry per character. The input strings are not modified.

    Edge cases and common mistakes

    • Different lengths. "ab" against "abb" returns false, because the sorted lists have different sizes.
    • Identical strings. A string is an anagram of itself, so isAnagram("abc", "abc") is true.
    • Same letters, different counts. "aab" and "abb" both contain a and b but sort to aab and abb, so the answer is false. Checking only that every letter of t appears in s would wrongly accept it.
    • Comparing arrays with ==. Returning s.toCharArray().sortedArray() == t.toCharArray().sortedArray() would be wrong even though both sides hold the same letters, because it compares array references. Use the lists, or call contentEquals.
    • Expecting the sort to change the string. Strings in Kotlin are immutable. There is no way to sort s in place, which is why the solution builds separate sorted copies.

    Testing

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