Start learning free

LESSON 229 OF 443 · SORTING

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

    SWIFT · SORTING

    Valid Anagram in Swift, explained

    Problem overview

    The function isAnagram receives two strings, s and t, and returns true when t can be made by rearranging the letters of s, using every letter exactly once. Both strings contain only lowercase English letters.

    For s = "anagram" and t = "nagaram" the answer is true: both have 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.

    The lesson asks for O(n log n) time, with O(n) extra space for the sorted copies. Faster solutions exist, but this one uses sorting.

    Approach: sort both, then compare

    Two words are anagrams exactly when they have the same letters with the same counts and differ only in order. Sorting removes the order. If both strings are sorted into alphabetical order, anagrams turn into identical sequences, and strings that aren't anagrams stay different.

    For "anagram" and "nagaram" the sorted form is aaagmnr for both. For "rat" and "car" the sorted forms are art and acr, which differ.

    The result is simple: sort s, sort t, and test whether the two sorted sequences are equal. Strings of different lengths can't be anagrams, and the comparison handles that without a special check, because sequences of different lengths are never equal.

    Step by step

    1. Sort s. let sortedS = s.sorted() creates a constant holding the sorted characters. let fits because the value is never changed after it is created.
    2. Sort t the same way into sortedT. Both strings get identical treatment so that the results can be compared position by position.
    3. Compare and return. sortedS == sortedT is true when the two arrays hold the same characters in the same order. Return that value directly.

    The solution in Swift

    func isAnagram(_ s: String, _ t: String) -> Bool {
    let sortedS = s.sorted()
    let sortedT = t.sorted()
    return sortedS == sortedT
}

    The Swift details worth a closer look:

    • sorted() returns a new array of Character. A String is a collection of characters, so "anagram".sorted() gives ["a", "a", "a", "g", "m", "n", "r"], an [Character], not a string. To get a string back you would write String(s.sorted()), which gives "aaagmnr", but the comparison doesn't need that step.
    • The original string is untouched. Strings in Swift are values, and sorted() never changes the thing it is called on. The in-place version for mutable collections is called sort(), and a String doesn't have it.
    • Arrays of characters compare with ==. Swift compares the lengths first and then the elements in order, so the result is false as soon as the arrays differ in length or in any position.
    • A function with no class. In this lesson isAnagram is a free function, not a method, so there is no Solution wrapper to write.
    • The _ before each parameter name means the call has no argument labels: isAnagram("rat", "car").
    • A single-expression return could skip the temporary constants, as in return s.sorted() == t.sorted(). The lesson keeps the named constants to show each step.

    Complexity

    Time: O(n log n + m log m), which is O(n log n) for strings of similar length. Here n and m are the lengths of s and t. Sorting s costs O(n log n), sorting t costs O(m log m), and comparing the two arrays walks them once, which is linear and smaller than the sorting.

    Space: O(n + m). sorted() builds a new array for each string, so the extra memory grows with the input. The sort needs no further notable space.

    Edge cases and common mistakes

    • Different lengths. isAnagram("a", "ab") is false. No length check is needed, because the two sorted arrays have different lengths.
    • Same letters, different counts. "aab" and "abb" use the same set of letters but are not anagrams. Sorting gives aab and abb, which differ. A solution that only compares which letters appear would get this wrong.
    • Identical strings. isAnagram("a", "a") is true. A string is an anagram of itself.
    • Sorting only one string. Sorting s alone and comparing it with the raw t returns false for "anagram" and "nagaram", because t is not in alphabetical order. Both sides need the same treatment.
    • Comparing a string with an array. s == t.sorted() doesn't compile, because one side is a String and the other an [Character]. Either sort both sides, or convert with String(...).
    • Indexing strings by integer. Code that tries s[0] fails, because a String can't be indexed with an Int. The sorted() approach avoids index arithmetic altogether.

    Testing

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