Valid Anagram Problem Solution

The valid anagram problem requires determining whether two strings contain the same characters in the same frequencies. This classic DSA problem tests understanding of string operations, hashing, and algorithmic optimization techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are the input strings guaranteed to be of equal length?
2. Can we assume the inputs only contain lowercase English letters, or should we handle Unicode characters?
3. Should we return a boolean value or perform some other operation?
4. Are we allowed to modify the input strings, or must we work with immutable copies?
5. What's the expected time complexity target - O(n) or better?

Restatement of the problem: Given two strings, determine whether one is an anagram of the other. An anagram means both strings contain exactly the same characters with identical frequencies, just arranged in different orders.

Input and Output specification:

• Input: Two strings s and t of equal length
• Output: Boolean value indicating whether t is an anagram of s
• Constraints: Both strings contain only lowercase English letters (assumed for this solution)

Assumptions made:

• Input strings are non-null and of equal length
• Only lowercase English letters (a-z) are present in the strings
• The solution should be case-sensitive

Data shape and hidden structure: The problem involves character frequency analysis where we need to verify that two strings have identical character counts. The underlying structure is a frequency distribution problem where we're essentially checking if two multisets of characters are equivalent.

The key insight is that an anagram is fundamentally about character frequency matching - if we can count how many times each character appears in both strings and they match exactly, then the strings are anagrams.

2. Pattern Recognition

The problem asks us to determine whether two strings are anagrams of each other - meaning they contain exactly the same characters with the same frequencies, just rearranged.

Pattern Identification:

• Character frequency matching: The core pattern here is that anagrams must have identical character frequencies
• Permutation problem: This is fundamentally about checking if one string is a permutation of another
• Counting and comparison: We need to count occurrences of each character and compare these counts

Wording Signals:

• "anagram" - directly signals we're looking for character frequency equivalence
• "same characters" - indicates the character set must be identical
• "rearranged" - suggests we're dealing with permutations rather than substring matching

Why This Fits The Pattern: This problem fits the character frequency counting pattern because:

1. We need to verify that both strings have exactly the same multiset of characters
2. The arrangement doesn't matter - only that character counts match
3. This is a classic "equivalence class" problem where we're checking if two strings belong to the same character frequency class

Core Insight: The key insight is that instead of generating all permutations (which would be O(n!)), we can simply count character frequencies in both strings and compare these counts. Two strings are anagrams if and only if their character frequency maps are identical.

This pattern appears in many string manipulation problems where we need to verify structural equivalence rather than ordering equivalence.

3. Approach Evolution

My first instinct is to check if two strings have the same characters with the same frequencies, which would mean they're anagrams. A naive approach would be to sort both strings and compare them directly - that's O(n log n) time complexity because sorting dominates the runtime. But let me think about how to optimize this.

Looking at the problem more carefully, I notice that we don't actually need to sort the entire strings - we just need to verify that each character appears the same number of times in both strings. This suggests a counting approach instead of sorting.

I notice that if I maintain a character frequency map for one string and then decrement counts while iterating through the second string, I can check if all counts are zero at the end. This approach would be O(n) time complexity where n is the length of the strings, which is much better than O(n log n).

The key insight here is that anagrams must have identical character frequencies - so instead of sorting to make the characters line up, I can just count occurrences and verify they match.

Let me think about this more systematically:

1. First approach: Sort both strings and compare - O(n log n) time, O(1) space (if we don't count the space used by sorting)
2. Second approach: Count character frequencies in one string, then decrement for the other - O(n) time, O(k) space where k is the size of character set

The second approach is clearly better for performance. I'll use a frequency array since we're dealing with lowercase English letters, which gives me O(1) space for the frequency tracking.

The invariant I need to maintain is that at any point during processing, if strings are anagrams, then the frequency array should have all zeros when we're done. If any character count becomes negative or positive, it means the strings aren't anagrams.

This approach works because:

• If both strings have same characters with same frequencies, all counts will be zero
• If one string has more of a character than the other, that count will become negative or positive
• If strings have different lengths, we'll detect it during iteration

This is the optimal linear time solution that avoids sorting overhead entirely.

4. Data Structure Choice

For this anagram validation problem, I'll use a HashMap as my primary data structure.

The HashMap is essential because:

1. It allows me to count character frequencies efficiently in O(1) average time
2. It provides a clean way to track which characters appear and how many times
3. It handles the mapping between characters and their counts naturally

I'll use a single HashMap with character keys and integer values to store the frequency count of each character in the first string. Then I'll iterate through the second string and decrement counts, ensuring no negative counts occur.

For the character counting approach, I'm choosing HashMap over arrays because:

• Arrays would require knowing the exact character set (assuming only lowercase letters a-z, which isn't specified)
• HashMap is more flexible and handles any valid character set
• It's more memory-efficient for sparse character distributions

The space complexity will be O(k) where k is the number of unique characters, which is optimal for this problem since we must account for all distinct characters that appear in the strings.

Helper structures:

• No additional helper structures needed beyond the HashMap
• The solution uses only one HashMap for character frequency counting

This choice enables an O(n) time complexity where n is the string length, and O(k) space where k is unique characters, which is optimal for this problem's requirements.

5. Algorithm Walkthrough

Let me trace through the solution with the example s = "anagram" and t = "nagaram".

Step 1: Initialize character frequency map with s string.

• Process 'a': count[0] = 1
• Process 'n': count[13] = 1
• Process 'a': count[0] = 2
• Process 'g': count[6] = 1
• Process 'r': count[17] = 1
• Process 'a': count[0] = 3
• Process 'm': count[12] = 1

Map after processing s: [3, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

Step 2: Process t string and decrement counts.

• Process 'n': count[13] = 0 (was 1)
• Process 'a': count[0] = 2 (was 3)
• Process 'g': count[6] = 0 (was 1)
• Process 'a': count[0] = 1 (was 2)
• Process 'r': count[17] = 0 (was 1)
• Process 'a': count[0] = 0 (was 1)
• Process 'm': count[12] = 0 (was 1)

Map after processing t: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Verify all counts are zero.

• All entries in the array are zero, so return true.

Edge case handling: If t had a different length than s, we'd return false immediately at the start. If any character in t was not present in s, we'd detect it when trying to decrement a zero count, but that's not possible since both strings have same length and same characters.

The algorithm terminates correctly because if two strings are anagrams, they must have identical character frequencies, and our approach ensures every character from s is matched exactly by characters from t.

6. Java Solution

public class Solution {
    public boolean isAnagram(String s, String t) {
        // Early exit: if lengths differ, they cannot be anagrams
        if (s.length() != t.length()) {
            return false;
        }
        
        // Use array to count character frequencies (assuming only lowercase letters)
        int[] charCount = new int[26];
        
        // Count characters in first string
        for (int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
        }
        
        // Subtract character counts based on second string
        for (int i = 0; i < t.length(); i++) {
            charCount[t.charAt(i) - 'a']--;
        }
        
        // Check if all counts are zero
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

This solution uses a fixed-size array to track character frequencies, which is optimal for the constrained case of only lowercase letters. The approach processes both strings in sequence and uses the difference in character counts to determine if they form an anagram.

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 in the input size.

Space Complexity: O(1)

While we use a HashMap to store character frequencies, the space usage is bounded by the size of the character set (typically 26 lowercase letters for English). Since this is a fixed constant regardless of input size, the space complexity is O(1) - constant space.

Why these bounds are correct:

The linear time complexity is optimal for this problem because we must examine each character at least once to determine if the strings are anagrams. Any algorithm that doesn't read all characters would miss potential mismatches.

The constant space complexity holds because:

1. The character set is bounded (e.g., 26 letters for lowercase English)
2. Even if we consider Unicode characters, the maximum possible unique characters is still bounded by the character set definition
3. The HashMap size never grows with input size, only with the fixed character set

Optimality:

This solution is optimal in both time and space. We cannot do better than O(n) time since we must read all characters, and we cannot use less than O(1) space since we need to store at least the character frequencies for a fixed character set. The solution achieves both bounds simultaneously, making it near-optimal for this problem.

The approach is optimal because:

• It avoids sorting (which would be O(n log n))
• It uses direct character counting instead of complex data structures
• It makes exactly one pass through the input data

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, while "a" and "b" should return `false"
• One empty, one non-empty: Empty string and any non-empty string should return false

Duplicate Values and Repeated States

• Duplicate characters: Strings like "aab" and "abb" should return false because character frequencies don't match
• Multiple duplicate characters: "aabb" vs "bbaa" should return true since both have same character counts

Boundary Conditions

• Null inputs: If either input is null, should handle gracefully (typically return false)
• Different string lengths: Should return false immediately when strings have different lengths
• Case sensitivity: The problem assumes case-sensitive comparison (e.g., "A" ≠ "a")

Common Implementation Mistakes

• Not checking string length: Failing to verify that both strings have the same length before processing
• Incorrect character counting: Using wrong data structures or logic that doesn't properly count character frequencies
• Array bounds issues: When using fixed-size arrays, ensuring indices don't go out of bounds
• Not resetting counters: When reusing data structures, ensuring they're properly reset between test cases
• Ignoring Unicode characters: Assuming ASCII-only input when the problem might involve Unicode characters (though this is less likely for basic anagram problems)

The most critical pitfall is assuming that equal-length strings automatically make valid anagrams without actually verifying character frequency matches.

9. Alternative Approaches

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

Approach 1: Sorting Approach

• Sort both strings and compare the results
• Time complexity: O(n log n) due to sorting
• Space complexity: O(n) for the sorted arrays
• This is simpler to implement but less efficient than the optimal O(n) solution

Approach 2: Character Frequency Map with Manual Counting

• Instead of using HashMap, manually maintain a fixed-size array of size 26 (for lowercase letters)
• For each character, increment/decrement the count in the array
• Time complexity: O(n)
• Space complexity: O(1) - fixed 26-element array
• This is more memory-efficient than HashMap for the specific case of lowercase English letters

Approach 3: Prime Product Method

• Assign prime numbers to each letter and multiply them
• If two strings are anagrams, their products will be equal
• Time complexity: O(n)
• Space complexity: O(1) - only storing the product
• This approach has mathematical elegance but suffers from potential integer overflow for longer strings

The chosen solution using HashMap is preferred because it's the most general and readable approach that works for any character set, while still maintaining optimal O(n) time complexity. The sorting approach is simpler but slower, and the prime product method introduces mathematical complexity and overflow risks.

The HashMap solution strikes the best balance between correctness, readability, and performance for a general anagram validation problem.

10. Test Cases

public class ValidAnagram {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        
        int[] charCount = new int[26];
        for (int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
            charCount[t.charAt(i) - 'a']--;
        }
        
        for (int count : charCount) {
            if (count != 0) return false;
        }
        return true;
    }
}

Sample Test Cases

Basic Valid Anagram:

• Input: s = "anagram", t = "nagaram"
• Expected: true
• Explanation: Both strings contain same characters with same frequencies

Basic Invalid Anagram:

• Input: s = "rat", t = "car"
• Expected: false
• Explanation: Different characters present

Empty Strings:

• Input: s = "", t = ""
• Expected: true
• Explanation: Two empty strings are valid anagrams

Single Character:

• Input: s = "a", t = "a"
• Expected: true
• Explanation: Identical single characters

Different Lengths:

• Input: s = "ab", t = "abc"
• Expected: false
• Explanation: Length mismatch immediately invalidates

Case Sensitivity:

• Input: s = "A", t = "a"
• Expected: false
• Explanation: 'A' and 'a' are different characters

Repeated Characters:

• Input: s = "aab", t = "abb"
• Expected: false
• Explanation: 'a' appears twice in first string but only once in second

Large Input Size:

• Input: s = "abcdefghijklmnopqrstuvwxyz", t = "zyxwvutsrqponmlkjihgfedcba"
• Expected: true
• Explanation: Same characters, different order

Tricky Edge Case - Unicode Characters:

// For Unicode support (not required for standard problem but worth mentioning)
public boolean isAnagramUnicode(String s, String t) {
    if (s.length() != t.length()) return false;
    
    Map<Character, Integer> charCount = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char c1 = s.charAt(i);
        char c2 = t.charAt(i);
        charCount.put(c1, charCount.getOrDefault(c1, 0) + 1);
        charCount.put(c2, charCount.getOrDefault(c2, 0) - 1);
    }
    
    return charCount.values().stream().allMatch(count -> count == 0);
}

Boundary Test Cases:

Single Character Strings:

• s = "a", t = "b" → false
• s = "x", t = "x" → true

Longest Possible Strings (assuming 5 * 10^4 constraint):

• Both strings of length 50000 with same character distribution
• Should handle efficiently without stack overflow

Special Characters:

• s = "a!b@c#", t = "#c@b!a"
• Expected: true (if case insensitive is not required)
• Expected: false (if case sensitive)

The test cases cover all major scenarios including basic functionality, edge cases, and performance considerations. The solution should handle all these cases efficiently with O(n) time complexity.

11. Final Summary

The core insight is that two strings are anagrams if and only if they contain exactly the same characters with identical frequencies. The most efficient approach uses a frequency counting method with O(n) time and O(1) space complexity, leveraging the fixed character set of lowercase English letters. This solution is optimal because we must examine each character at least once to determine anagram status, making the linear time complexity unavoidable. The elegance lies in using a single array as a frequency map to track character differences, which elegantly handles all edge cases including empty strings and single characters through the fundamental property that anagrams must have identical character distributions.