Start learning free

LESSON 227 OF 441 · SORTING

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

    C# · SORTING

    Valid Anagram in C#, explained

    Problem overview

    The method IsAnagram receives two strings, s and t, and returns true when t can be formed by rearranging the letters of s, using every letter exactly once. Both strings hold lowercase letters, and each has between 1 and 50,000 of them.

    "anagram" and "nagaram" are anagrams, so the result is true. "rat" and "car" are not: the letters differ, so the result is false.

    Approach: sort both, then compare

    Two words are anagrams when they contain the same letters with the same counts, and only the order differs. Sorting removes the order. If you sort the letters of both words, anagrams turn into identical strings, and non-anagrams don't.

    For "anagram" and "nagaram", both sort to aaagmnr, so they match. For "rat" and "car" the sorted forms are art and acr, which differ.

    The lesson asks for O(n log n) time and O(n) extra space for the sorted copies. Counting the letters instead of sorting them takes O(n) time and has its own lesson; sorting is the simplest to write and reason about.

    Step by step

    1. Copy s into a char[] and sort it. A C# string is immutable, so it can't be sorted in place. s.ToCharArray() returns a new array of its letters, and Array.Sort(sortedS) sorts that array in place, in ascending order.
    2. Do the same for t, into sortedT. Both strings get the same treatment, so equal letters end up at equal positions.
    3. Compare the two arrays item by item with sortedS.SequenceEqual(sortedT) and return the result. It is true only when both arrays have the same length and the same letter at every position.

    The solution in C#

    class Solution {
    public bool IsAnagram(string s, string t) {
        char[] sortedS = s.ToCharArray();
        Array.Sort(sortedS);
        char[] sortedT = t.ToCharArray();
        Array.Sort(sortedT);
        return sortedS.SequenceEqual(sortedT);
    }
}

    The C# details worth knowing:

    • Why not == on the arrays? For arrays, == asks whether both variables refer to the very same array object. Two separate arrays with identical letters give false. SequenceEqual compares the contents instead. Strings are different: == on two string values compares their characters.
    • Different lengths. SequenceEqual returns false for "ab" and "abb", since one array has an item more. That also handles the case where the strings have different lengths and so can't be anagrams.
    • SequenceEqual is a LINQ method. It comes from System.Linq, and Array is in System, so a standalone file needs using System; and using System.Linq; at the top.
    • Array.Sort returns nothing. It reorders the array you give it and returns void. Writing char[] sortedS = Array.Sort(s.ToCharArray()); doesn't compile.
    • The original strings are untouched. Sorting works on the copies. After the call, s and t still hold their original letters.
    • How letters sort. char values sort by their numeric code, so 'a' comes before 'b'. For lowercase letters this is alphabetical order.

    Complexity

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

    Time: O(n log n + m log m). Sorting s costs O(n log n) and sorting t costs O(m log m). Copying the letters and comparing the two sorted arrays are both linear and don't change the total.

    Space: O(n + m). The two char[] copies hold every letter of both strings.

    Edge cases and common mistakes

    • Different lengths. "ab" and "abb" returns false. A comparison that only looks at the letters of the shorter array would wrongly accept them.
    • Same letters, different counts. "aab" and "abb" have the same length and the same set of letters but are not anagrams: their sorted forms are aab and abb.
    • Identical strings. A string is an anagram of itself, so "abc" and "abc" returns true.
    • Comparing arrays with ==. This compiles but returns false for two separate arrays, even when they hold the same letters.
    • Forgetting to sort one of them. Sorting only s compares a sorted array with a shuffled one, which almost never matches.
    • Missing using System.Linq;. Without it, SequenceEqual isn't found and the code doesn't compile.

    Testing

    • "anagram", "nagaram" gives true.
    • "rat", "car" gives false.
    • "ab", "abb" gives false.
    • "abc", "abc" 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