Check if Two Strings Are Anagrams (Sorting or Frequency Array) - Java

@Note: This is categorized as “Difficult” because it requires sorting comparisons, bitwise offsets, and constant space array allocation techniques that fresher candidates often struggle to implement.

---

Category: Difficult | Concepts used: Sorting comparison, frequency array comparison

---

Problem Statement

Two strings are anagrams if one can be rearranged to form the other — they contain exactly the same characters with the same frequencies.

Input : "listen", "silent"      Output: true
Input : "hello", "world"          Output: false

Examples (with edge scenarios)

#	String A	String B	Output	Why
1	"listen"	"silent"	true	Same letters, rearranged
2	"hello"	"world"	false	Different letter compositions
3	""	""	true	Both empty — trivially anagrams of each other
4	"abc"	"ab"	false	Different lengths can never be anagrams
5	"Listen"	"Silent"	Depends on case sensitivity — clarify!	'L' vs 'l' — case matters unless normalized

Common Fresher Mistake

Mistake	What happens	Fix
Not checking string lengths first	Unnecessary work comparing strings that obviously can’t match (different lengths can NEVER be anagrams)	Quick early-exit: if lengths differ, return false immediately
Forgetting to normalize case and/or spaces (for phrase-based anagrams like “listen” vs “silent” but also “William Shakespeare” style checks)	May incorrectly report false due to case/space mismatches	Clarify requirements: exact character match, or normalized (lowercase, spaces ignored)?

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Playing Scrabble

Imagine you are playing Scrabble and want to verify if the word on the board "silent" is an anagram of the tiles in your hand "listen":

• Solution 1 (Sorting): You sort all the letters in both words alphabetically on your rack:
  • Board word becomes: e, i, l, n, s, t.
  • Your hand tiles become: e, i, l, n, s, t.
  • Since both sorted racks look identical, they are anagrams!
• Solution 2 (The Scorecard Checklist): You have a scorecard sheet listing letters A through Z with a count of 0 next to each.
  • As you scan the board word "silent", you add a check mark to each letter’s row (+1).
  • Simultaneously, as you scan your hand tiles "listen", you cross off one check mark from the corresponding letter’s row (-1).
  • At the end of your check, if every letter row has exactly 0 check marks, you have successfully confirmed that no letters are extra or missing!

---

Solution 1 — Sort Both Strings and Compare

Intuition

If two strings are anagrams, they contain exactly the same characters — just in different order. Sorting both strings arranges their characters into a canonical order; if they’re truly anagrams, their sorted versions must be character-for-character identical.

import java.util.Arrays;

public class AnagramSort {
    public static boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) {
            return false; // quick early exit
        }

char[] charsA = a.toCharArray();
        char[] charsB = b.toCharArray();
        Arrays.sort(charsA);
        Arrays.sort(charsB);

return Arrays.equals(charsA, charsB);
    }

public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent")); // true
        System.out.println(isAnagram("hello", "world"));     // false
        System.out.println(isAnagram("", ""));                 // true
    }
}

Output:

true
false
true

Dry Run (a=“listen”, b=“silent”)

charsA sorted = [e,i,l,n,s,t]
charsB sorted = [e,i,l,n,s,t]
Arrays.equals -> identical -> true

Interviewer’s take

This is a clean, easy-to-explain solution — O(n log n) due to sorting, which is perfectly acceptable for most interview settings. Arrays.sort()/Arrays.equals() are standard tools here, not shortcuts that avoid the underlying logic.

Follow-up questions you might get:

• “Can you do this in O(n) time instead of O(n log n)?” → leads to Solution 2.

---

Solution 2 — Using a Frequency Array (O(n), No Sorting, Recommended)

Intuition

Instead of sorting to compare character compositions, directly count how many times each letter appears in string A using a small fixed-size array (26 slots for lowercase English letters). Then, as we scan string B, decrement the corresponding slot for each character it contains. If the two strings are true anagrams, every increment from A should be perfectly cancelled out by a matching decrement from B — leaving every slot at exactly 0 by the end.

public class AnagramFrequencyArray {
    public static boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }

int[] freq = new int[26]; // assumes lowercase English letters only

for (int i = 0; i < a.length(); i++) {
            freq[a.charAt(i) - 'a']++; // count characters in A
            freq[b.charAt(i) - 'a']--; // "un-count" characters in B
        }

// if truly anagrams, every slot should have returned to exactly 0
        for (int count : freq) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent")); // true
        System.out.println(isAnagram("hello", "world"));     // false
    }
}

Output:

true
false

Dry Run (a=“abc”, b=“cab”)

freq[26] all start at 0

i=0: a[0]='a' -> freq['a'-'a'=0]++ -> freq[0]=1
     b[0]='c' -> freq['c'-'a'=2]-- -> freq[2]=-1
i=1: a[1]='b' -> freq[1]++ -> freq[1]=1
     b[1]='a' -> freq[0]-- -> freq[0]=0
i=2: a[2]='c' -> freq[2]++ -> freq[2]=0
     b[2]='b' -> freq[1]-- -> freq[1]=0

Final freq array: all zeros -> true  (anagrams confirmed)

Interviewer’s take

This is the preferred optimized answer — O(n) time, and only O(1) extra space (a fixed 26-slot array, regardless of input length) — better than the O(n) space needed for sorting’s character array copies. The “increment for A, decrement for B, check all zero” trick is elegant and commonly reused in anagram-family problems. Note the assumption: this specific version only handles lowercase English letters — worth mentioning as a limitation, with a HashMap<Character, Integer> as the natural generalization for full Unicode/mixed-case support.

Follow-up questions you might get:

• “What if the strings can contain uppercase letters or Unicode characters?” → Either normalize to lowercase first (if case shouldn’t matter), or replace the fixed int[26] array with a HashMap<Character, Integer> to support any character set generally.
• “Why is this considered O(1) space when Solution 1 is O(n)?” → The frequency array here has a fixed size (26), independent of input length — true constant extra space; sorting, by contrast, needs O(n) space for the character array copies (which scale with input size).

---

📊 Visual Flowchart

graph TD
    Start["Given Strings a and b"] --> LengthCheck{"a.length == b.length?"}
    LengthCheck -->|No| RetFalse["Return False"]
    LengthCheck -->|Yes| Strategy{"Choose Strategy"}
    Strategy -->|Sort & Compare| SortPath["Sort char arrays charsA and charsB"]
    SortPath --> CompArrays["Compare sorted arrays"]
    CompArrays --> RetResult["Return result"]
    Strategy -->|Frequency Checklist| FreqPath["Initialize freq[26] array"]
    FreqPath --> Loop{"i < a.length?"}
    Loop -->|Yes| IncDec["freq[a[i] - 'a']++<br>freq[b[i] - 'a']--"]
    IncDec --> Next["i++"]
    Next --> Loop
    Loop -->|No| CheckZeros{"All slots in freq == 0?"}
    CheckZeros -->|Yes| RetTrue["Return True"]
    CheckZeros -->|No| RetFalse

---

Final Verdict — Which Solution Should You Give?

• Both are considered strong answers — Solution 1 is perfectly fine for most interviews, but Solution 2 is the better, more optimized answer, especially if time/space complexity is discussed.

---

Quick Recap

Approach	Time	Space	Handles full Unicode?
Sort + Arrays.equals()	O(n log n)	O(n)	Yes, naturally
Frequency array (int[26])	O(n)	O(1)	Lowercase-only as written (extend with HashMap for general case)