Start learning free

LESSON 224 OF 438 · SORTING

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

    JAVA · SORTING

    Valid Anagram in Java, explained

    Problem overview

    The method isAnagram(String s, String t) returns 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 words have three a's and one each of g, m, n and r. For s = "rat" and t = "car" the answer is false, since t has a c where s has a t.

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

    Approach: sorting removes the order

    Two words are anagrams exactly when they have the same letters with the same counts. Only the order differs, and order is the one thing sorting throws away. After sorting, an anagram pair becomes two identical rows of letters, and a pair that isn't an anagram stays different:

    s = "anagram"  sorted: aaagmnr
t = "nagaram"  sorted: aaagmnr   -> equal, so anagrams

s = "rat"      sorted: art
t = "car"      sorted: acr       -> different, so not anagrams

    So the whole solution is to sort both strings and compare. Strings of different lengths can never be anagrams, and the final comparison handles that without extra code.

    Step by step

    1. Copy s into a char[] and sort it. A Java String is immutable and can't be sorted, so toCharArray() builds a new array holding its letters. Arrays.sort then orders that array in place. The original string stays as it was.
    2. Do the same for t, into its own array, so the two rows can be compared position by position.
    3. Compare the arrays with Arrays.equals. It checks the lengths first and then each letter in turn, and returns the answer directly.

    The solution in Java

    class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sortedS = s.toCharArray();
        Arrays.sort(sortedS);
        char[] sortedT = t.toCharArray();
        Arrays.sort(sortedT);
        return Arrays.equals(sortedS, sortedT);
    }
}

    The code uses java.util.Arrays, so a standalone file needs import java.util.Arrays; (or java.util.*) at the top.

    The Java details worth a look:

    • Arrays are compared with Arrays.equals. Using == on two arrays asks whether they are the very same array in memory, and so does the equals method that arrays inherit. For two separate arrays holding a and b, both sortedS == sortedT and sortedS.equals(sortedT) are false even when the contents match. Arrays.equals(sortedS, sortedT) compares the contents.
    • Sorting works on the array, not the string. There is no Arrays.sort(s) for a String: it doesn't compile. The copy into char[] is what makes sorting possible.
    • Characters sort by their code. Arrays.sort on a char[] orders letters by character code, which for lowercase English letters is alphabetical order.
    • An alternative ending. new String(sortedS).equals(new String(sortedT)) gives the same answer, but builds two more objects. Comparing the arrays directly is simpler.

    Complexity

    Time: O(n log n + m log m), where n and m are the lengths of s and t. Sorting each array costs that much, and the final comparison is linear. When the lengths are equal, which is the only case that can return true, this is O(n log n).

    Space: O(n + m). The two sorted arrays are copies of the input strings. Sorting itself may use some extra working memory on top of that, which doesn't change the total.

    Edge cases and common mistakes

    • Different lengths. isAnagram("ab", "abc") is false: Arrays.equals returns false for arrays of different lengths.
    • Same letters, different counts. "aab" and "abb" have the same set of letters but are not anagrams. Sorting gives aab and abb, which differ. Comparing only which letters appear would get this wrong.
    • Identical strings. A word is an anagram of itself, so isAnagram("abc", "abc") is true.
    • Forgetting to sort one of the strings. Comparing a sorted array with an unsorted one fails for almost every input.
    • Comparing with ==. It compiles and returns false every time, even for identical contents.

    Testing

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