Anagram Check Techniques in DSA Java

Mental Model

Two words are anagrams if they have the exact same letters in any order.

Analogy: Think of two bags of letter tiles from a word game; if both bags have the same letters in the same amounts, they are anagrams.

word1: c -> a -> t -> null
word2: t -> a -> c -> null

Dry Run Walkthrough

Input: word1: "listen", word2: "silent"

Goal: Check if the two words are anagrams by comparing their letters

Step 1: Convert both words to character arrays

listen: [l, i, s, t, e, n]
silent: [s, i, l, e, n, t]

Why: We need to work with letters individually to compare them

Step 2: Sort both character arrays alphabetically

listen sorted: [e, i, l, n, s, t]
silent sorted: [e, i, l, n, s, t]

Why: Sorting puts letters in order so we can compare positions directly

Step 3: Compare sorted arrays letter by letter

All letters match at each position

Why: If all letters match, words are anagrams

Result:

listen sorted: e -> i -> l -> n -> s -> t -> null
silent sorted: e -> i -> l -> n -> s -> t -> null
Result: Anagrams

Annotated Code

DSA Java

import java.util.Arrays;

public class AnagramCheck {

    public static boolean areAnagrams(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false; // Different lengths can't be anagrams
        }
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        Arrays.sort(arr1); // Sort letters of first word
        Arrays.sort(arr2); // Sort letters of second word
        return Arrays.equals(arr1, arr2); // Compare sorted arrays
    }

    public static void main(String[] args) {
        String word1 = "listen";
        String word2 = "silent";
        boolean result = areAnagrams(word1, word2);
        System.out.println("Result: " + (result ? "Anagrams" : "Not Anagrams"));
    }
}

if (word1.length() != word2.length()) {

Check if words have different lengths -- quick elimination

char[] arr1 = word1.toCharArray();

Convert first word to array of letters

char[] arr2 = word2.toCharArray();

Convert second word to array of letters

Arrays.sort(arr1);

Sort letters of first word alphabetically

Arrays.sort(arr2);

Sort letters of second word alphabetically

return Arrays.equals(arr1, arr2);

Compare sorted arrays to confirm if all letters match

Output

Result: Anagrams

Complexity Analysis

Time: O(n log n) because sorting each word of length n takes O(n log n)

Space: O(n) for storing character arrays of the words

vs Alternative: Counting letter frequencies can achieve O(n) time but requires extra space for frequency arrays

Edge Cases

Empty strings

Returns true because two empty words are trivially anagrams

DSA Java

if (word1.length() != word2.length()) {

Words with different lengths

Returns false immediately without sorting

DSA Java

if (word1.length() != word2.length()) {

Words with same letters but different cases (e.g., "Listen" vs "silent")

Returns false because case differs; needs preprocessing to handle case-insensitive

DSA Java

No explicit guard; preprocessing needed before this method

When to Use This Pattern

When you need to check if two words have the same letters in any order, use sorting or frequency counting to detect anagrams efficiently.

Common Mistakes

Mistake: Comparing words directly without sorting or counting letters
Fix: Sort both words or count letter frequencies before comparing

Mistake: Ignoring case differences leading to false negatives
Fix: Convert both words to the same case (e.g., lowercase) before checking

Summary

Checks if two words have exactly the same letters in any order.

Use when you want to know if two words are rearrangements of each other.

Sorting letters puts them in order so comparing becomes simple and direct.

Practice

1. What does it mean if two strings are anagrams of each other?

easy

A. They end with the same character

B. They have the same length but different characters

C. They start with the same character

D. They contain the same characters in any order

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, using all original letters exactly once.

2. Step 2: Compare character sets

   If two strings have the same characters with the same frequency, they are anagrams regardless of order.

3. Final Answer:

   They contain the same characters in any order -> Option D

4. Quick Check:

   Anagrams = same characters any order [OK]

Hint: Check if sorted strings match to confirm anagrams [OK]

Common Mistakes:

• Thinking same length means anagrams
• Only comparing first or last characters
• Ignoring character frequency

2. Which Java code snippet correctly checks if two strings s1 and s2 are anagrams using sorting?

easy

A. char[] a1 = s1.toCharArray(); char[] a2 = s2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2);

B. Arrays.sort(s1.toCharArray()); Arrays.sort(s2.toCharArray()); return s1.equals(s2);

C. return s1.equalsIgnoreCase(s2);

D. return s1.length() == s2.length();

Solution

1. Step 1: Convert strings to char arrays and sort

   We must convert strings to char arrays because Arrays.sort works on arrays, not strings.

2. Step 2: Compare sorted arrays for equality

   After sorting, if arrays are equal, strings are anagrams. Use Arrays.equals to compare arrays.

3. Final Answer:

   char[] a1 = s1.toCharArray(); char[] a2 = s2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); -> Option A

4. Quick Check:

   Sort char arrays and compare arrays [OK]

Hint: Sort char arrays, then compare with Arrays.equals [OK]

Common Mistakes:

• Sorting strings directly without converting to char arrays
• Using equals() on unsorted strings
• Comparing only lengths

3. What will be the output of the following Java code?

String s1 = "listen";
String s2 = "silent";
char[] a1 = s1.toCharArray();
char[] a2 = s2.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
System.out.println(Arrays.equals(a1, a2));

medium

A. Runtime exception

B. false

C. true

D. Compilation error

Solution

1. Step 1: Convert and sort both strings

   Both strings "listen" and "silent" are converted to char arrays and sorted. Sorted arrays become ['e','i','l','n','s','t'] for both.

2. Step 2: Compare sorted arrays

   Since sorted arrays are identical, Arrays.equals(a1, a2) returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Sorted arrays match = true [OK]

Hint: Sort and compare arrays to check anagrams [OK]

Common Mistakes:

• Assuming order matters without sorting
• Confusing equals() on strings with arrays
• Forgetting to sort arrays

4. Identify the error in this Java method that checks if two strings are anagrams:

public boolean isAnagram(String s1, String s2) {
  if (s1.length() != s2.length()) return false;
  char[] a1 = s1.toCharArray();
  char[] a2 = s2.toCharArray();
  Arrays.sort(a1);
  Arrays.sort(a2);
  return a1.equals(a2);
}

medium

A. Using a1.equals(a2) compares references, not content

B. Missing length check before sorting

C. Sorting arrays is incorrect for anagram check

D. Method should return void, not boolean

Solution

1. Step 1: Understand array equality in Java

   Using a1.equals(a2) compares if both arrays are the same object, not their contents.

2. Step 2: Use correct method to compare arrays

   To compare contents, use Arrays.equals(a1, a2) instead of a1.equals(a2).

3. Final Answer:

   Using a1.equals(a2) compares references, not content -> Option A

4. Quick Check:

   Use Arrays.equals() for array content comparison [OK]

Hint: Use Arrays.equals() to compare array contents [OK]

Common Mistakes:

• Using equals() on arrays instead of Arrays.equals()
• Ignoring length check
• Returning wrong data type

5. You want to check if two strings are anagrams but ignoring case and spaces. Which approach is best?

hard

A. Compare strings directly with equalsIgnoreCase()

B. Remove spaces, convert to lowercase, then sort and compare char arrays

C. Count characters without removing spaces or changing case

D. Check if lengths are equal and first characters match

Solution

1. Step 1: Normalize strings by removing spaces and converting to lowercase

   Removing spaces and converting to lowercase ensures uniform comparison ignoring case and spaces.

2. Step 2: Sort char arrays and compare

   After normalization, convert to char arrays, sort them, and compare to check anagram status.

3. Final Answer:

   Remove spaces, convert to lowercase, then sort and compare char arrays -> Option B

4. Quick Check:

   Normalize then sort and compare [OK]

Hint: Normalize strings before sorting to ignore case and spaces [OK]

Common Mistakes:

• Not removing spaces before comparison
• Ignoring case differences
• Only comparing lengths or first characters