Start learning free

LESSON 228 OF 442 · SORTING

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

    GO · SORTING

    Valid Anagram in Go, explained

    Problem overview

    isAnagram(s string, t string) returns true when t can be formed by rearranging all the letters of s, using each letter exactly as many times as it appears, and false otherwise. Both strings hold lowercase English letters only.

    For s = "anagram" and t = "nagaram" the answer is true: the two words use the same letters in a different order. For s = "rat" and t = "car" it is false, because t has a c where s has a t.

    Approach: sorting removes the order

    Two words are anagrams when they differ only in the order of their letters. Sorting takes the order away. After sorting, two anagrams become the same string, and two words that aren't anagrams stay different.

    For "anagram" and "nagaram", both sort to "aaagmnr". For "rat" and "car", the sorted forms are "art" and "acr", which differ. If the strings have different lengths, the sorted strings differ in length and are never equal, so no separate length check is needed.

    The cost is dominated by the two sorts, O(n log n) each. The lesson accepts that price. A faster solution counts the letters instead of sorting them, and it has its own lesson.

    Step by step

    1. Copy s into a byte slice with []byte(s), named sortedS. A Go string can't be changed in place, so sorting needs a mutable copy of its bytes. Each lowercase English letter takes exactly one byte, so the slice holds exactly the letters.
    2. Sort it with sort.Slice. It takes the slice and a function less(i, j), which reports whether the item at position i belongs before the item at position j. Here that is sortedS[i] < sortedS[j], which sorts the bytes in ascending order.
    3. Do the same for t: a byte slice named sortedT, sorted the same way. Both strings need identical treatment so that their results can be compared.
    4. Compare the results as strings. Convert each slice back with string(...) and compare with ==. The result of that comparison is the return value.

    The solution in Go

    func isAnagram(s string, t string) bool {
    sortedS := []byte(s)
    sort.Slice(sortedS, func(i, j int) bool { return sortedS[i] < sortedS[j] })
    sortedT := []byte(t)
    sort.Slice(sortedT, func(i, j int) bool { return sortedT[i] < sortedT[j] })
    return string(sortedS) == string(sortedT)
}

    The Go details worth a closer look:

    • The import. sort.Slice lives in the sort package, so a program that uses this function needs import "sort". Without it, the build fails.
    • Strings are immutable. Assigning to a position of a string, as in s[0] = 'x', doesn't compile (cannot assign to s[0]). Converting with []byte(s) makes a new slice with a copy of the bytes, so sorting it leaves the original s untouched.
    • The less function is a closure. The function literal func(i, j int) bool { ... } refers to sortedS, a variable of the enclosing function. sort.Slice passes it positions, not values, so the function reads the items itself.
    • Slices can't be compared with ==. Writing sortedS == sortedT fails with slice can only be compared to nil. Converting both to strings gives something Go can compare, byte by byte. A loop over the two slices would work too, and so would bytes.Equal.
    • Bytes versus characters. Sorting bytes is correct here only because every letter is one byte. A string with accented or other non-ASCII letters has several bytes per character, and sorting the bytes would mix them up. The constraints rule that case out.

    Complexity

    Time: O(n log n + m log m), where n and m are the lengths of s and t. Each sort costs a length times its logarithm. Comparing two strings costs at most the length of the shorter one, which is smaller than the sorting cost. When the lengths are equal, this is O(n log n).

    Space: O(n + m). The two byte slices are copies of the inputs. Converting them back to strings for the comparison may allocate copies as well, which stays within the same bound.

    Edge cases and common mistakes

    • Different lengths. "ab" and "abc" sort to "ab" and "abc", which are different, so the answer is false.
    • Repeated letters. "aab" and "abb" contain the same distinct letters, but the counts differ, so the sorted strings "aab" and "abb" differ. Checking only which letters appear would answer true wrongly.
    • Same word. A string is an anagram of itself, and the function returns true.
    • Sorting the original. A string can't be sorted directly. Copy it into a byte slice first.
    • Wrong direction in the less function. Both strings are sorted by the same function, so either ascending or descending would give a correct answer, as long as both use the same one. Mixing the two would break the comparison.
    • Comparing slices directly. Convert to strings first, or compare element by element.

    Testing

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