Anagram Problem - Complete Solution Guide
Problem Statement
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.
Table of Contents
1. Approach 1: Sorting Method
2. Approach 2: HashMap/Frequency Count
3. Approach 3: Array Frequency Count (Most Optimized)
4. Approach 4: Greedy Optimized with Early Termination
5. Approach 5: Mathematical Sum Approach
6. Approach 6: Unicode Support Version
7. Approach 7: Stream API Approach
8. Performance Analysis
9. Recommendations
Approach 1: Sorting Method
Time Complexity: O(n log n)
Space Complexity: O(1) excluding sorting space
Best for: Readability and small input sizes
java
public static boolean isAnagramSorting(String s, String t) {
if (s.length() != t.length()) return false;
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
Arrays.sort(sArr);
Arrays.sort(tArr);
return Arrays.equals(sArr, tArr);
}
Explanation: Convert both strings to character arrays, sort them, and compare. If they're equal
after sorting, they're anagrams.
Pros:
Simple and intuitive
Easy to understand and implement
Works with any character set
Cons:
Not the most efficient due to O(n log n) sorting
Requires additional space for character arrays
Approach 2: HashMap/Frequency Count
Time Complexity: O(n)
Space Complexity: O(k) where k is number of unique characters
Best for: Unicode characters and variable character sets
java
public static boolean isAnagramHashMap(String s, String t) {
if (s.length() != t.length()) return false;
HashMap<Character, Integer> map = new HashMap<>();
// Count characters in string s
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
// Decrease count for characters in string t
for (char c : t.toCharArray()) {
if (!map.containsKey(c)) return false;
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) {
map.remove(c);
}
}
return map.isEmpty();
}
Explanation: Count frequency of each character in the first string, then decrement for each
character in the second string. If all counts become zero, they're anagrams.
Pros:
Linear time complexity
Works with any character set including Unicode
Flexible and extensible
Cons:
Uses additional space proportional to unique characters
HashMap operations have slight overhead
Approach 3: Array Frequency Count (Most Optimized)
Time Complexity: O(n)
Space Complexity: O(1) - constant space for 26 letters
Best for: Performance with known character set (ASCII lowercase)
java
public static boolean isAnagramArrayCount(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26]; // assuming only lowercase letters
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
Explanation: Use a fixed-size array to count character frequencies. Increment for characters in
first string, decrement for second string. If all counts are zero, they're anagrams.
Pros:
Most efficient for ASCII characters
Constant space complexity
Single pass through both strings
Cache-friendly due to array access
Cons:
Limited to specific character sets (needs modification for Unicode)
Assumes lowercase letters only
Approach 4: Greedy Optimized with Early Termination
Time Complexity: O(n)
Space Complexity: O(1)
Best for: Cases where early termination is beneficial
java
public static boolean isAnagramGreedyOptimized(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
int nonZeroCount = 0; // track how many characters have non-zero count
for (int i = 0; i < s.length(); i++) {
char sChar = s.charAt(i);
char tChar = t.charAt(i);
// Update count for character from s
if (count[sChar - 'a'] == 0) nonZeroCount++;
count[sChar - 'a']++;
if (count[sChar - 'a'] == 0) nonZeroCount--;
// Update count for character from t
if (count[tChar - 'a'] == 0) nonZeroCount++;
count[tChar - 'a']--;
if (count[tChar - 'a'] == 0) nonZeroCount--;
}
return nonZeroCount == 0;
}
Explanation: Tracks the number of characters with non-zero counts. This approach can
potentially identify non-anagrams earlier in some cases.
Pros:
Potential for early termination
Single pass through strings
Constant space complexity
Cons:
More complex logic
Overhead of tracking non-zero count
May not always be faster in practice
Approach 5: Mathematical Sum Approach
Time Complexity: O(n)
Space Complexity: O(1)
Best for: Theoretical interest (limited practical use)
java
public static boolean isAnagramSum(String s, String t) {
if (s.length() != t.length()) return false;
long sumS = 0, sumT = 0;
long prodS = 1, prodT = 1;
for (int i = 0; i < s.length(); i++) {
sumS += s.charAt(i);
sumT += t.charAt(i);
prodS *= s.charAt(i);
prodT *= t.charAt(i);
}
return sumS == sumT && prodS == prodT;
}
Explanation: Uses mathematical properties (sum and product) to check if strings are anagrams.
Pros:
Very fast constant time operations
Minimal space usage
Cons:
Risk of integer overflow
Potential hash collisions (different strings with same sum/product)
Not reliable for all cases
Approach 6: Unicode Support Version
Time Complexity: O(n)
Space Complexity: O(1) - constant for Unicode range
Best for: Full Unicode character support
java
public static boolean isAnagramUnicode(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[Character.MAX_VALUE + 1];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
count[t.charAt(i)]--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
Explanation: Similar to array count but supports full Unicode character range.
Pros:
Supports all Unicode characters
Linear time complexity
Single pass through strings
Cons:
Large memory footprint for array
Wasteful if only using small subset of characters
Approach 7: Stream API Approach
Time Complexity: O(n log n)
Space Complexity: O(n)
Best for: Functional programming style
java
public static boolean isAnagramStream(String s, String t) {
if (s.length() != t.length()) return false;
return Arrays.equals(
s.chars().sorted().toArray(),
t.chars().sorted().toArray()
);
}
Explanation: Uses Java 8 Streams to sort and compare character arrays.
Pros:
Functional programming style
Concise and readable
Leverages Java 8 features
Cons:
Not the most efficient
Creates intermediate arrays
Stream overhead
Performance Analysis
Time Complexity Comparison
Approach Time Complexity Space Complexity Best Use Case
Sorting O(n log n) O(1) Small inputs, readability
HashMap O(n) O(k) Unicode support
Array Count O(n) O(1) ASCII characters, performance
Greedy Optimized O(n) O(1) Early termination potential
Mathematical O(n) O(1) Theoretical (unreliable)
Unicode Array O(n) O(1) Full Unicode support
Stream API O(n log n) O(n) Functional style
Performance Ranking (Best to Worst)
1. Array Count - Most optimized for ASCII
2. HashMap - Best balance of performance and flexibility
3. Greedy Optimized - Good with early termination
4. Unicode Array - Good for Unicode but large memory
5. Sorting - Simple but slower
6. Stream API - Readable but not optimal
7. Mathematical - Fast but unreliable
Recommendations
For Coding Interviews/LeetCode
Use Approach 3 (Array Count) - it's the most optimized and expected solution:
java
public static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
For Production Code
ASCII/Lowercase only: Use Array Count approach
Unicode support needed: Use HashMap approach
Performance critical: Profile and choose between Array Count and HashMap
For Learning
Start with Approach 1 (Sorting) as it's most intuitive, then progress to more optimized solutions.
Complete Test Suite
java
public class AnagramTest {
public static void main(String[] args) {
// Test cases
testCase("anagram", "nagaram", true);
testCase("rat", "car", false);
testCase("", "", true);
testCase("a", "a", true);
testCase("ab", "ba", true);
testCase("abc", "def", false);
// Performance test
performanceComparison();
}
private static void testCase(String s, String t, boolean expected) {
boolean result = isAnagram(s, t);
System.out.println(String.format("isAnagram(\"%s\", \"%s\") = %b (Expected
s, t, result, expected, result == expected ? "✓" : "✗"));
}
private static void performanceComparison() {
String s = "abcdefghijklmnopqrstuvwxyz".repeat(1000);
String t = "zyxwvutsrqponmlkjihgfedcba".repeat(1000);
System.out.println("\nPerformance Comparison (1000 iterations):");
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
isAnagramArrayCount(s, t);
}
System.out.println("Array Count: " + (System.nanoTime() - start) / 1000000
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
isAnagramHashMap(s, t);
}
System.out.println("HashMap: " + (System.nanoTime() - start) / 1000000 + "
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
isAnagramSorting(s, t);
}
System.out.println("Sorting: " + (System.nanoTime() - start) / 1000000 + "
}
}
Key Takeaways
1. Array Count approach is the most optimized for ASCII characters
2. HashMap approach offers the best balance of performance and flexibility
3. Sorting approach is the most intuitive for beginners
4. Always check string lengths first as an early optimization
5. Consider the character set requirements when choosing an approach
6. For interviews, be prepared to discuss trade-offs between approaches
This document provides a comprehensive analysis of all major approaches to solve the anagram
problem in Java, with detailed explanations, complexity analysis, and practical recommendations.
