Start learning free

LESSON 223 OF 437 · SORTING

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

    C++ · SORTING

    Valid Anagram in C++, explained

    Problem overview

    The method isAnagram receives two strings, s and t, and returns a bool: true when t can be formed by rearranging the letters of s, using every letter exactly as many times as it appears, and false otherwise. Both strings hold lowercase English letters and each has at least one and at most 50,000 characters.

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

    This lesson asks for O(n log n) time and O(n) extra space for sorted copies of the two strings. Faster counting solutions exist and come in later lessons.

    Approach: sorting removes the order

    Two words are anagrams when they differ only in the order of their letters. So the order is the one thing to get rid of. Sorting does exactly that: once the letters of each word are in alphabetical order, any two anagrams turn into the same string.

    For "anagram" and "nagaram" both sorted strings are "aaagmnr", so they are equal. For "rat" and "car" the sorted strings are "art" and "acr", which differ.

    The check is correct because two strings that contain the same letters, each the same number of times, have the same sorted form, and two strings with a different count for some letter have different sorted forms. Strings of different lengths can't match either, since a sorted string keeps its length. So no separate length check is needed.

    The cost is dominated by the two sorts, each O(n log n), followed by one linear comparison. The brute-force alternative of trying every rearrangement of one string would be hopelessly slow, and counting letters, shown in a later lesson, reaches O(n).

    Step by step

    1. Sort s in place with sort(s.begin(), s.end()). The two iterators mark the whole string. The method's s is its own copy, since the parameter is taken by value, so the caller's string stays as it was.
    2. Sort t the same way. Both words must get identical treatment for their sorted forms to be comparable.
    3. Return s == t. The == operator on std::string compares lengths and then characters, so it is true only when both strings hold the same characters in the same order.

    The solution in C++

    class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

    C++ details worth a closer look:

    • Iterator ranges. s.begin() points at the first character and s.end() points one past the last. The range is half-open, so sort handles everything from the first character through the last.
    • sort works in place. It rearranges the characters of the string it is given and returns nothing. That is why the solution calls it as a statement and then compares the strings themselves.
    • By-value parameters. Because s and t are copies, sorting them can't affect the caller. The copies are also the O(n) extra space the lesson mentions. With const string& parameters you would have to copy the strings yourself before sorting.
    • Characters sort by code. A char compares as a small integer, and the lowercase letters have increasing codes from 'a' to 'z', so sorting gives alphabetical order.
    • == compares contents. Unlike comparing pointers to C-style strings, == on two std::string objects compares the text they hold.

    Complexity

    Time: O(n log n). Each sort call takes O(n log n) comparisons in the worst case, and the final comparison is O(n). The sorts dominate.

    Space: O(n). The by-value parameters are two copies of the input, and these are the strings that get sorted. std::sort itself needs only a small amount of extra memory.

    Edge cases and common mistakes

    • Different lengths. "ab" and "abc" give false: the sorted strings have different lengths, so == is false.
    • Same letters, different counts. "aab" and "abb" contain the same set of letters but not the same counts. Their sorted forms are "aab" and "abb", which differ. A check that only asks whether each letter of one string occurs somewhere in the other would say true here.
    • Identical strings. A string is an anagram of itself, so "abc" and "abc" return true.
    • Sorting only one string. If only s were sorted, it would almost never equal an unsorted t. Both must be sorted.
    • Forgetting that sort returns nothing. Writing return sort(s.begin(), s.end()) == ... doesn't compile, because sort returns void.
    • Using the end iterator wrongly. s.end() is already one past the last character. Passing s.end() - 1 would leave the last character out of the sort.

    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.
    • s = "a", t = "a" gives true.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free