Breaking Down Anagrams: The Uniform Approach

Let's take two very simple inputs: Mary and Army.

How do we know that these two strings are anagrams? Well, we can keep track of both their letters and see if they match. The big idea is how to do the tracking-- can we do it in a uniform way that's intuitive?

Common Ground: What Makes Them the Same?

To determine if two strings are anagrams, we need to establish if they contain the exact same collection of letters. Think of it as two different piles of building blocks—each block is a letter, and we want to verify if both piles are made from the same set of blocks.

The Difference Maker: Ordering

If the difference between two potential anagrams is just the ordering of their letters, then it should stand to reason that sorting the letters would make them look the same.

Voilà! We've stumbled upon our core strategy: sort the strings and then compare.

Sensitivity Training: Case Matters (Or Does It?)

To make our comparison agnostic to letter casing, we'll convert all characters in both strings to lowercase.

Illustrated Concept

Here's a visual guide to help you understand:

The Code: Making It Happen

Step 1: Convert to Lowercase

First, let's bring both strings to common ground by converting them to lowercase.

1String a = str1.toLowerCase();
2String b = str2.toLowerCase();

The Art of Sorting: The Final Frontier in Anagram Detection

Why Sorting?

After normalizing the case of each string, the next logical step is to sort the characters. Sorting them will line up the characters in each string like soldiers in formation, ready for a face-to-face comparison.

Why a String over an Array?

In some programming languages, comparing arrays requires a deep equality check. Strings, however, can be compared easily using basic equality operators. By sorting and then joining the array of characters back into a string, we reduce the problem to a simpler string comparison.

Step 2: Sorting and Joining for Direct Comparison

Once the strings are in lowercase, we sort the characters in each string and then join them back into new strings. This transformation ensures that if the strings are anagrams, they will now be identical.

1char[] aArray = a.toCharArray();
2char[] bArray = b.toCharArray();
3Arrays.sort(aArray);
4Arrays.sort(bArray);
5return Arrays.equals(aArray, bArray);

Wrapping It Up

If the transformed strings are equal, it implies the original strings are anagrams of each other. If not, they are as unrelated as 'earth' is to 'heart', except in anagram land, where they are, in fact, twins separated at birth!

Complexity Analysis: What's the Cost?

Time Complexity: A Closer Look

Our choice to employ the built-in sorting methods contributes the most to our time complexity. Sorting operations generally have a time complexity of $O\left(n\log n\right)$. All other operations we've performed—such as string manipulation and array joining—are more or less constant time operations, leaving sorting as the primary driver of computational cost.

Space Complexity: How Roomy?

In terms of space, we've created additional arrays or lists to hold the sorted characters from each string. This memory allocation grows linearly with the size of the input strings, resulting in a space complexity of $O\left(n\right)$.

The Final Tally

So, there you have it: the complete breakdown of our anagram detection algorithm. It's efficient in terms of space, but the sorting step does add a logarithmic factor to the time complexity. Keep these considerations in mind when weighing this method against alternatives for your specific use case.

One Pager Cheat Sheet

• Write a method isAnagram(str1, str2) to check if two strings are anagrams of each other, given that they contain only alphanumeric characters and have a length of up to 100000, with an expected time and space complexity of O(nlogn) and O(n), respectively.
• We can use lowercase and sorting to efficiently determine if two strings, such as Mary and Army, are anagrams.
• By splitting, sorting and joining the characters in each string, we can easily compare the raw characters present to determine if two strings are anagrams.
• This algorithm has an O(n log n) time complexity and O(n) space complexity.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

import static org.junit.Assert.*;

​

import java.util.Arrays;

import java.util.Arrays;

import org.junit.*;

import org.junit.runner.*;

import org.junit.runner.notification.*;

​

public class MainTest {

​

  public static boolean isAnagram(String word, String anagram) {

    char[] charFromWord = word.toLowerCase().toCharArray();

    char[] charFromAnagram = anagram.toLowerCase().toCharArray();

    Arrays.sort(charFromWord);

    Arrays.sort(charFromAnagram);

    return Arrays.equals(charFromWord, charFromAnagram);

  }

​

  // tests

​

  @Test

  public void firstTest() {

    assertEquals(MainTest.isAnagram("Mary", "Army"), true);

  }

​

  @Test

  public void secondTest() {

    assertEquals(MainTest.isAnagram("cinema", "iceman"), true);

  }

​

  @Test

  public void thirdTest() {

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.