Valid Anagram Solution Patterns and Implementation

Valid anagram problems require determining whether two strings contain the same characters in identical frequencies, presenting multiple algorithmic approaches with distinct trade-offs in efficiency and implementation complexity.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are the input strings guaranteed to be non-null and non-empty?
2. Do we need to consider case sensitivity (e.g., are "A" and "a" considered the same character)?
3. What is the expected return format - should we return a boolean or can we mutate the input?
4. Are there any constraints on string length (e.g., < 10^6 characters)?
5. Should the follow-up solution aim for O(n) time complexity?

Restatement of the pattern: The Valid Anagram problem asks us to determine whether two strings contain exactly the same characters with identical frequencies. This is a canonical string matching problem where we need to verify that one string is a permutation of another.

Signal words and constraint shape: Key indicators include "anagram", "same characters", "permutation", and "character frequency". The constraint shape typically involves comparing two string inputs where character counts must match exactly. Problems often specify that only lowercase letters (or ASCII characters) are involved, and the strings must have equal length.

Assumptions made:

• Both input strings are valid (non-null)
• We're working with ASCII or lowercase English letters only
• The strings can be mutated if needed (though we'll avoid this for cleaner solutions)
• Return type is boolean indicating validity

Pattern suitability: This pattern is best suited for static scenarios where both inputs are available upfront. It's not appropriate for streaming data where one string arrives in chunks or where we need to process strings in real-time with unknown future inputs. The problem is fundamentally about static comparison rather than online processing.

The core insight is that two strings are anagrams if and only if they contain the same characters with identical frequencies - this can be efficiently verified through character counting approaches.

2. When to Use This Pattern

Signal words and constraint shapes:

• "anagram" or "rearrangement" of characters
• Character frequency comparison between strings
• Input size constraints (typically up to 10^5 characters)
• Need to determine if two strings are permutations of each other
• Character set limited to lowercase letters (a-z) or ASCII characters

Why this pattern fits better than alternatives: This pattern is specifically suited for anagram problems because it directly addresses the core requirement of character frequency matching. Compared to alternatives like sorting both strings (O(n log n)) or using hash maps for character counting, the frequency array approach is more efficient and cleaner. The key insight that makes this pattern work is that two strings are anagrams if and only if they contain exactly the same characters with identical frequencies.

Conditions where variations apply:

• When strings can contain Unicode characters, we'd need to use HashMap instead of fixed-size arrays
• For very large character sets or sparse character distributions, hash maps might be more memory-efficient
• When dealing with streams of characters rather than complete strings, we'd need a streaming approach

The core insight: Two strings are anagrams if and only if their character frequency distributions are identical. This allows us to reduce the problem from comparing two strings to comparing two frequency arrays, which is a direct one-to-one mapping that's both intuitive and efficient.

The pattern works particularly well when:

1. Character set is known and bounded (like lowercase English letters)
2. Input size is moderate to large (where O(n) solutions matter)
3. We're comparing exact character matches rather than approximate similarity
4. The problem asks for a boolean result rather than detailed character analysis

3. Approach Evolution

Interview communication script:

My first instinct is to check if two strings are anagrams by sorting their characters and comparing the results, because that seems like a straightforward way to verify if they contain exactly the same letters with the same frequencies. But that's O(n log n) because sorting takes logarithmic time per character, and I'm not sure if that's optimal.

Let me think about how to optimize this. I notice that an anagram means both strings have the same character frequencies, so instead of sorting, I could count character frequencies directly. If I maintain a frequency map or array and increment for one string and decrement for the other, I can verify that all counts are zero at the end.

That would reduce it to O(n) time complexity, which is much better than O(n log n). The key insight is that I don't need to sort at all - I just need to ensure character counts match between both strings.

Let me trace through this approach: I'll use a fixed-size array to count character frequencies (assuming lowercase English letters), iterate through both strings once, incrementing for one and decrementing for the other, then verify all counts are zero.

Brute-force approach and why it is not ideal:

The brute-force approach would be to sort both strings character-by-character and compare the sorted results. This works but has O(n log n) time complexity due to sorting, and requires O(n) extra space for the sorted arrays. It's not ideal because it's inefficient for large inputs and unnecessarily complex when we only care about character frequency matching.

Improved approach and the key optimization:

The improved approach uses a character frequency counting technique with a fixed-size array (for lowercase letters, size 26). The key optimization is avoiding sorting entirely by maintaining a running count of each character's frequency. For each character in the first string, we increment its count in our array, and for each character in the second string, we decrement that count. If the strings are anagrams, all counts should be zero at the end.

Final approach with step-by-step reasoning:

1. First validate that both strings have equal length - if not, they cannot be anagrams
2. Create a frequency array of size 26 (for lowercase English letters) initialized to zero
3. Iterate through both strings simultaneously:
   • For each character in string1, increment the corresponding index in frequency array
   • For each character in string2, decrement the corresponding index in frequency array
4. Check that all values in frequency array are zero - if yes, they're anagrams; otherwise, not anagrams

This approach is optimal because it makes exactly one pass through each string and uses constant space for the character array, achieving O(n) time and O(1) space complexity.

Important invariants that must hold:

• Both strings must have equal length for an anagram check to be valid
• The character frequency array must have all zero values at the end of processing
• Each character index in the frequency array corresponds to a specific letter (a-z) and is accessed using ASCII arithmetic: char - 'a'

4. Data Structure Choice

For the valid anagram problem, I'll use a frequency count approach with either:

1. HashMap<Character, Integer> - to track character frequencies
2. int[26] array - for lowercase English letters only

Primary Data Structures Used:

HashMap<Character, Integer> is the primary choice because:

• It handles arbitrary character sets (not just lowercase letters)
• Provides O(1) average lookup and update operations
• Allows natural representation of character frequency differences
• Works seamlessly with Java's built-in collections

int[26] array is a viable alternative when:

• Input is guaranteed to contain only lowercase English letters (a-z)
• Memory efficiency is critical
• Performance is slightly better due to direct indexing vs hash computation

Why Each Choice Is Needed:

The HashMap approach is more flexible and handles edge cases better:

• Can work with Unicode characters, special symbols, or mixed case
• No need to predefine character ranges
• Easier to extend for international text or extended ASCII

The array approach is more efficient in the constrained case:

• O(1) access time vs O(log n) hash lookup
• No hash collision handling needed
• Lower memory overhead (no hash table structures)

Time and Space Impact:

HashMap approach:

• Time: O(n) for building frequency map, O(1) for lookups
• Space: O(k) where k is the number of unique characters (at most 256 for ASCII)

Array approach:

• Time: O(n) for building frequency array, O(1) for lookups
• Space: O(1) - fixed 26-element array regardless of input size

Helper Structure:

I'll use a single HashMap to maintain character frequency differences, which simplifies the logic and avoids needing separate structures for counting up and down.

The choice between HashMap and array is primarily about input constraints rather than algorithmic complexity - both approaches maintain the same O(n) time complexity for the core operation.

5. Algorithm Walkthrough

Let me trace through the solution with a concrete example to show how it works step by step.

Example: s = "anagram", t = "nagaram"

Step 1: Verify input constraints

• Both strings have equal length (7 characters each)
• Strings contain only lowercase letters
• This is a valid input for our solution

Step 2: Initialize character frequency map

• Create HashMap to store character counts
• Map will track: {a: 0, n: 0, g: 0, r: 0, m: 0}

Step 3: Process first string "anagram"

• Character 'a': map.get('a') = 0 → update to 1
• Character 'n': map.get('n') = 0 → update to 1
• Character 'a': map.get('a') = 1 → update to 2
• Character 'g': map.get('g') = 0 → update to 1
• Character 'r': map.get('r') = 0 → update to 1
• Character 'a': map.get('a') = 2 → update to 3
• Character 'm': map.get('m') = 0 → update to 1

Step 4: Process second string "nagaram"

• Character 'n': map.get('n') = 1 → update to 0
• Character 'a': map.get('a') = 3 → update to 2
• Character 'g': map.get('g') = 1 → update to 0
• Character 'a': map.get('a') = 2 → update to 1
• Character 'r': map.get('r') = 1 → update to 0
• Character 'a': map.get('a') = 1 → update to 0
• Character 'm': map.get('m') = 1 → update to 0

Step 5: Final validation

• All values in map are zero: {a: 0, n: 0, g: 0, r: 0, m: 0}
• Return true - strings are anagrams

Edge case handling: If we had s = "ab", t = "aa":

• After processing s: {a: 1, b: 1}
• After processing t: {a: 0, b: 1}
• Since 'b' count is not zero, return false

The algorithm correctly handles all character frequency mismatches and terminates when all character counts balance to zero.

6. Java Solution

public class ValidAnagram {
    public boolean isAnagram(String s, String t) {
        // Early exit: if lengths differ, they cannot be anagrams
        if (s.length() != t.length()) {
            return false;
        }
        
        // Use frequency array for 26 lowercase letters
        int[] charFrequency = new int[26];
        
        // Count frequency of each character in string s
        for (int i = 0; i < s.length(); i++) {
            charFrequency[s.charAt(i) - 'a']++;
        }
        
        // Decrease count for each character in string t
        for (int i = 0; i < t.length(); i++) {
            charFrequency[t.charAt(i) - 'a']--;
        }
        
        // Check if all frequencies are zero
        for (int i = 0; i < 26; i++) {
            if (charFrequency[i] != 0) {
                return false;
            }
        }
        
        return true;
    }
}

This solution uses a fixed-size frequency array to track character counts. For each character in the first string, we increment its count in the array, then decrement for each character in the second string. If they are anagrams, all counts should return to zero.

The approach assumes only lowercase English letters (a-z), which allows us to use a simple array instead of a HashMap for better performance. The solution handles the core requirement efficiently with O(n) time and O(1) space complexity.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input strings.

The solution makes a single pass through each string to count character frequencies, and then performs a constant-time comparison of the two frequency maps. Since we're iterating through each string exactly once and the map operations (put/get) are O(1) on average, the overall time complexity is linear.

Space Complexity: O(k) where k is the size of the character set (typically 26 for lowercase letters, or 128 for ASCII).

In the optimal solution using character frequency counting, we maintain a fixed-size array or HashMap to store character counts. For ASCII characters, this is O(128) = O(1), and for extended character sets like Unicode, it's O(k) where k is the number of unique characters in the input.

Why these bounds are correct:

• The linear time complexity is optimal because we must examine each character at least once to determine if the strings are anagrams
• The space complexity is bounded by the character set size, which is constant for standard ASCII or a reasonable fixed-size Unicode range
• We don't need to sort or perform nested iterations, so the complexity is as good as it gets for this problem

Optimality:

This solution is optimal in both time and space complexity. Any algorithm that determines if two strings are anagrams must examine each character at least once (Ω(n)), and the space required to store character counts is bounded by the character set size. The solution achieves O(n) time and O(1) space for practical character sets, making it near-optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty strings: Both empty strings should return true as they are valid anagrams of each other
• Single character: Single character strings like "a" and "a" should return true
• One empty, one non-empty: Empty string and non-empty string should return false

Duplicate Values and Repeated States

• Duplicate characters: Strings like "aab" and "abb" should return false (different character frequencies)
• Multiple duplicate characters: "aabbcc" and "abcabc" should return true (same character frequencies)
• Case sensitivity: "AaBb" and "bBaA" should return false (case matters in this problem)

Boundary Conditions

• Null inputs: Handle null string parameters gracefully (typically throw IllegalArgumentException)
• Different lengths: Strings of different lengths should immediately return false
• Very long strings: Performance matters for large inputs (should be O(n) time complexity)

Common Implementation Mistakes

• Not handling case sensitivity: Assuming strings are already lowercase or ignoring case differences
• Incorrect frequency counting: Using incorrect data structures or logic that doesn't properly track character counts
• Missing null checks: Failing to validate inputs before processing
• Failing to handle Unicode characters: Assuming ASCII-only input when dealing with international text
• Incorrect return logic: Returning true for different length strings or not properly checking all character frequencies

// Example of proper null handling:
if (s == null || t == null) {
    return false;
}

9. Alternative Approaches

There are several alternative approaches to solving the valid anagram problem, each with different trade-offs:

1. Sorting Approach: Sort both strings and compare them directly. This is O(n log n) time complexity due to sorting, but uses O(1) extra space if we sort in-place. This approach is simpler to implement but less efficient than the character counting method.

2. HashMap-based Character Counting: Use a HashMap to count character frequencies in both strings, then compare the maps. This is O(n) time but uses O(k) space where k is the number of unique characters. It's more flexible for handling Unicode characters but requires more memory than the fixed-size array approach.

3. Character Frequency Array (Optimized): Use a fixed-size array of 26 integers for lowercase letters only. This is O(n) time and O(1) space, making it optimal for the specific constraint of lowercase English letters. It's more efficient than HashMap but only works with limited character sets.

4. Prime Product Approach: Assign prime numbers to each character and compute the product of primes for each string. If products match, strings are anagrams. This is O(n) time but has potential integer overflow issues and requires precomputed primes.

The chosen solution using fixed-size array is optimal for the specific constraints (lowercase English letters) as it provides O(n) time complexity with minimal space overhead and no overflow concerns. The sorting approach is simpler but slower, while HashMap offers more flexibility at the cost of additional space.

The alternative approaches are viable but generally less optimal than the chosen solution for the specific problem constraints.

10. Test Cases

import java.util.*;

public class ValidAnagramTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic valid anagram
        // Input: s = "anagram", t = "nagaram"
        // Expected: true
        System.out.println("Test 1: " + new Solution().isAnagram("anagram", "nagaram"));
        
        // Test case 2: Basic invalid anagram
        // Input: s = "rat", t = "car"
        // Expected: false
        System.out.println("Test 2: " + new Solution().isAnagram("rat", "car"));
        
        // Test case 3: Different lengths
        // Input: s = "ab", t = "abc"
        // Expected: false
        System.out.println("Test 3: " + new Solution().isAnagram("ab", "abc"));
        
        // Test case 4: Empty strings
        // Input: s = "", t = ""
        // Expected: true
        System.out.println("Test 4: " + new Solution().isAnagram("", ""));
        
        // Test case 5: Single character
        // Input: s = "a", t = "a"
        // Expected: true
        System.out.println("Test 5: " + new Solution().isAnagram("a", "a"));
        
        // Test case 6: Case sensitivity
        // Input: s = "A", t = "a"
        // Expected: false
        System.out.println("Test 6: " + new Solution().isAnagram("A", "a"));
        
        // Test case 7: With duplicates
        // Input: s = "aab", t = "abb"
        // Expected: false
        System.out.println("Test 7: " + new Solution().isAnagram("aab", "abb"));
        
        // Test case 8: Same characters, different counts
        // Input: s = "aa", t = "aaa"
        // Expected: false
        System.out.println("Test 8: " + new Solution().isAnagram("aa", "aaa"));
        
        // Test case 9: Unicode characters
        // Input: s = "你好", t = "好你"
        // Expected: true
        System.out.println("Test 9: " + new Solution().isAnagram("你好", "好你"));
    }
}

Sample Test Cases:

1. Basic Valid Anagram: s = "anagram", t = "nagaram" → true
2. Basic Invalid Anagram: s = "rat", t = "car" → false
3. Different Lengths: s = "ab", t = "abc" → false
4. Empty Strings: s = "", t = "" → true
5. Single Character: s = "a", t = "a" → true
6. Case Sensitivity: s = "A", t = "a" → false
7. Duplicate Characters: s = "aab", t = "abb" → false
8. Different Counts: s = "aa", t = "aaa" → false
9. Unicode Characters: s = "你好", t = "好你" → true

Tricky Edge Cases:

• Length mismatch: When strings have different lengths, they cannot be anagrams
• Character frequency mismatch: Same length but different character counts
• Case sensitivity: 'A' and 'a' are not the same character
• Unicode handling: Non-ASCII characters must be handled correctly

Boundary Cases:

• Empty strings (both empty)
• Single character strings
• Very long strings (performance testing)
• Strings with only one unique character

11. Final Summary

The core idea is to efficiently determine if two strings are anagrams by comparing their character frequency distributions. The solution works by leveraging a fixed-size frequency array to count character occurrences, which enables O(n) time and O(1) space complexity for the comparison.

What makes this solution efficient is that it eliminates the need for sorting or hash maps by taking advantage of the constrained character set (lowercase English letters). The approach is optimal because we must examine each character at least once to make the comparison, and the fixed-size array lookup provides constant-time operations throughout the process.

The key insight is that anagrams must have identical character frequencies, so we can reduce the problem to a frequency counting comparison rather than requiring string reordering or complex data structure operations. This makes the solution both time and space optimal for the given constraints.