Good evening! Here's our prompt for today.
Understanding Anagrams: A Simple Definition
An anagram is a fascinating literary device where you can rearrange the letters of a word, phrase, or name to form another meaningful sequence. Think of it as a jigsaw puzzle made of letters. For example, the word "cinema" can be rearranged to form "iceman."
The Challenge: Detecting Anagrams
Problem Statement
Given two input strings like "cinema" and "iceman," your task is to implement a method called isAnagram(str1, str2)
. This method should return true
if the given strings are anagrams of each other and false
otherwise.
Constraints to Consider
Computational Limits
The length of both input strings will be less than or equal to 100,000.
Character Rules
The input strings will only contain alphanumeric characters (
a-z, A-Z, 0-9
).
Performance Expectations
- The expected time complexity for this operation is
O(nlogn)
. - The expected space complexity is
O(n)
.
Empty Strings are Valid
- The input strings can be empty. Imagine that as a puzzle with no pieces; it's trivially solvable!
Coding the Solution
Given the constraints and expectations, you'll need to think carefully about your algorithm. The aim is not just to solve the problem, but to solve it efficiently within the given computational and space boundaries.
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
import static org.junit.Assert.*;
import org.junit.*;
import org.junit.runner.*;
import org.junit.runner.notification.*;
public class MainTest {
public static boolean isAnagram(String inputA, String inputB) {
// fill in
// with solution
return inputA;
}
// tests
public void firstTest() {
assertEquals(MainTest.isAnagram("Mary", "Army"), true);
}
public void secondTest() {
assertEquals(MainTest.isAnagram("cinema", "iceman"), true);
}
public void thirdTest() {
assertEquals(MainTest.isAnagram("jake", "jay"), false);
Here's a video of us explaining the solution.
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...
How do I use this guide?
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 . 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 .
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 asMary
andArmy
, are anagrams. - By
splitting
,sorting
andjoining
the characters in each string, we can easilycompare
theraw characters
present to determine if two strings areanagrams
. - This algorithm has an
O(n log n)
time complexity andO(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
public void firstTest() {
assertEquals(MainTest.isAnagram("Mary", "Army"), true);
}
public void secondTest() {
assertEquals(MainTest.isAnagram("cinema", "iceman"), true);
}
public void thirdTest() {
Got more time? Let's keep going.
If you had any problems with this tutorial, check out the main forum thread here.