Start learning free

LESSON 231 OF 445 · SORTING

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

    RUST · SORTING

    Valid Anagram in Rust, explained

    Problem overview

    The function is_anagram receives two owned strings, s and t, and returns a bool: true when t can be formed by rearranging the letters of s, using every letter exactly once, and false otherwise. Both strings hold lowercase English letters and have between 1 and 50,000 characters.

    For s = "anagram" and t = "nagaram" the answer is true: both strings contain three a, 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 and O(n) extra space for the sorted copies. Faster approaches exist, but this lesson is about sorting.

    Approach: sorting removes the order

    An anagram has the same letters as the original in a different order. If you sort both strings, the order is gone and only the letters are left, so two anagrams turn into the same sorted sequence. In the example, "anagram" and "nagaram" both become aaagmnr. The strings "rat" and "car" become art and acr, which differ.

    So the check is: sort both, then compare. Two sorted sequences are equal exactly when they contain the same letters with the same counts. Strings of different lengths can never match, and that case needs no separate check, as the comparison handles it by itself.

    Step by step

    1. Collect the letters of s into a vector. A String in Rust has no sort method, because it stores UTF-8 text, not a plain array of letters. Calling s.chars().collect() into a Vec<char> gives something that can be sorted. The variable is named sorted_s and is mut, because sorting rearranges it in place.
    2. Sort it with sort(). The characters are ordered by their code points, which for lowercase letters is alphabetical order.
    3. Do the same for t with a vector named sorted_t. Both strings get identical treatment, so their sorted forms can be compared position by position.
    4. Return the comparison sorted_s == sorted_t. Two vectors are equal when they have the same length and the same elements in the same order.

    The solution in Rust

    impl Solution {
    fn is_anagram(s: String, t: String) -> bool {
        let mut sorted_s: Vec<char> = s.chars().collect();
        sorted_s.sort();
        let mut sorted_t: Vec<char> = t.chars().collect();
        sorted_t.sort();
        return sorted_s == sorted_t;
    }
}

    Run on the examples, it returns true for ("anagram", "nagaram") and false for ("rat", "car").

    The Rust details worth a closer look:

    • collect() needs a target type. The annotation Vec<char> on the variable tells collect() what to build. Without it, the compiler can't decide which collection you want.
    • sort() works in place and returns (). It changes the vector it is called on, so the vector has to be mut, and the call is a statement of its own. Writing let v = x.sort(); would give you the unit value, not a sorted vector.
    • Strings can't be sorted directly. Calling s.sort() on a String is a compile error: no method named sort found for struct String. Go through a Vec of characters or bytes.
    • chars() or bytes(). For lowercase English letters, collecting bytes into a Vec<u8> and sorting that works equally well. The lesson uses char, which also stays correct for text outside ASCII.
    • Vectors compare with ==. The comparison goes element by element and stops at the first difference. A different length is an immediate mismatch.
    • Ownership. The function takes String by value, but chars() only borrows, so s and t are untouched. The sorted vectors are new, separate copies.

    Complexity

    Let n be the length of s and m the length of t.

    Time: O(n log n + m log m). Collecting each string is linear, sorting costs O(n log n) and O(m log m), and the final comparison is at most linear. When the lengths are equal, which is the only case that can be an anagram, this is O(n log n).

    Space: O(n + m). The two vectors hold one char per letter. They are the sorted copies the lesson mentions.

    Edge cases and common mistakes

    • Different lengths. ("a", "ab") gives false. The vectors differ in length, so they can't be equal.
    • Same letters, different counts. ("aab", "abb") gives false. A check that only asks "does every letter of t appear in s?" would wrongly say true. Sorting keeps the counts.
    • Identical strings. ("a", "a") gives true: a string is an anagram of itself.
    • Sorting only one of the strings. The unsorted vector is in original order, so the comparison would depend on how the letters were arranged, not on which letters they are.
    • Forgetting mut. Calling sort() on a vector declared without mut is a compile error.

    Testing

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