Find All Anagrams in a String Algorithm Solution

The anagram finding problem requires identifying all starting indices where a pattern's anagrams appear in a target string. This classic sliding window approach efficiently solves the problem by maintaining character frequency counts and comparing windows.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input strings contain only lowercase letters, or could they include uppercase letters and special characters?
2. What is the expected time complexity constraint? Are we aiming for O(n) or O(n log n)?
3. Should we return the indices in sorted order, or can they be returned in any order?
4. Are we allowed to mutate the input strings, or must we work with immutable copies?
5. How large can the input strings be in terms of length?

Restated problem: Given two strings s and p, find all the start indices in s where an anagram of p appears as a substring. An anagram is a rearrangement of the letters in another string with the same character frequencies.

Input and output details:

• Input: Two strings s (the search string) and p (the pattern string)
• Output: A list of integers representing the start indices in s where an anagram of p is found
• Constraints:
  • Length of s can be up to 10⁵
  • Length of p can be up to 10⁴
  • Both strings contain only lowercase English letters

Assumptions made:

• The input strings contain only lowercase English letters (a-z)
• We can return the indices in any order
• The input strings are not null or empty (we'll handle edge cases explicitly)
• We're looking for exact anagram matches, not partial matches

Data shape and hidden structure: The problem involves a sliding window pattern where we need to check character frequency matches across substrings of fixed length. The key insight is that an anagram has the same character frequencies as the pattern string, so we can use a frequency map approach to efficiently compare substrings without generating all permutations.

The problem has a hidden structure where we're essentially looking for all contiguous substrings of s that have the same character frequency distribution as p. This suggests a sliding window approach with fixed-size windows, which can be optimized using character frequency counting.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern for this problem is sliding window technique combined with hash map frequency counting.

Why this fits the pattern

The problem asks us to find all starting indices where a substring of the input string matches the character frequency pattern of the given pattern string. This is a classic "find all substrings with specific properties" problem where:

1. We're looking for exact character frequency matches (anagrams)
2. The search space is a sliding window of fixed size (length of pattern string)
3. We need to maintain and compare character counts efficiently
4. The problem has a clear "window" that moves through the input string

Core insight needed to solve it

The key insight is that two strings are anagrams if and only if they contain exactly the same characters with the same frequencies. This means we can:

• Count character frequencies in the pattern string
• Use a sliding window of size equal to pattern length over the input string
• At each window position, compare the character frequency of that window with the pattern's character frequency
• When they match, we've found an anagram starting at that position

This transforms the problem from checking all possible substrings (O(n²)) to maintaining a fixed-size sliding window with O(1) frequency comparisons at each step.

3. Approach Evolution

My first instinct is to use a sliding window approach because we're looking for all occurrences of anagrams in a string, which naturally suggests maintaining a window of fixed size (equal to the length of the pattern). But that's O(n²) in the worst case because for each position, we'd need to check if the substring is an anagram of the pattern, which requires sorting or counting characters.

Let me think about how to optimize this. I notice that if I maintain character frequency counts for both the pattern and current window, I can reduce it to O(n) by using a sliding window technique with constant-time character updates. The key insight is that an anagram means the same characters appear with the same frequencies, so instead of comparing sorted strings, I can compare character frequency maps.

The approach I'll use:

1. Create a frequency map for the pattern string
2. Use a sliding window of size equal to pattern length over the input string
3. For each window, maintain a frequency map and compare it with the pattern's frequency map
4. When maps match, we've found an anagram

This is O(n) time because:

• We process each character at most twice (once when expanding window, once when contracting)
• Character frequency comparisons are O(1) since we have at most 26 lowercase letters

The invariant I must maintain is that the sliding window always contains exactly the length of the pattern string, and at each step I'm comparing character frequencies between current window and pattern.

This approach is optimal because we must examine each character at least once to determine if it's part of an anagram, and the sliding window technique ensures we don't do redundant work.

The key optimization is using character frequency maps instead of sorting or string comparison, which reduces the per-window check from O(k log k) to O(1) where k is the pattern length.

4. Data Structure Choice

For this problem, I'll use a sliding window approach with frequency counting.

Primary Data Structures

1. HashMap/Array for character frequency counting:

   • Used to track character frequencies in the pattern string (p) and current window in s
   • Time: O(1) for lookups/updates, Space: O(k) where k is the alphabet size (at most 26 for lowercase letters)
   • I'll use an array of size 26 instead of HashMap for better performance since we're dealing with only lowercase letters

2. ArrayList for result storage:

   • Stores starting indices where anagrams are found
   • Time: O(1) for append operations, Space: O(n) where n is the number of valid anagrams

Why These Choices Are Optimal

The array-based frequency counter is preferred over HashMap because:

• Constant time access and updates (O(1) vs O(log k))
• No hash collision overhead
• Predictable memory layout
• For lowercase English letters, array size is manageable (26 elements)

The ArrayList is the natural choice for collecting results since:

• We don't know beforehand how many anagrams we'll find
• It provides efficient append operations and indexed access
• No need for complex resizing logic

Helper Structures

I'll use a sliding window technique where:

• Two pointers (left and right) define the current window in string s
• A counter tracks how many characters match their required frequency in pattern p

This approach avoids creating additional copies of substrings, maintaining O(1) space complexity for the window tracking.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Example: s = "cbaebabacd", p = "abc"

Step 1: Initialize variables

• sLen = 10, pLen = 3
• windowStart = 0
• charCount map for pattern: {a:1, b:1, c:1}
• matches = 0 (number of characters that match frequency requirement)
• windowCharCount map for current window

Step 2: Expand window to size pLen (3)

• i=0: Add 'c' → windowCharCount = {c:1}, matches = 0 (no match yet)
• i=1: Add 'b' → windowCharCount = {c:1, b:1}, matches = 0 (no match yet)
• i=2: Add 'a' → windowCharCount = {c:1, b:1, a:1}, matches = 3 (all characters match frequency)

Step 3: Found first anagram at index 0, add to result: result = [0]

Step 4: Slide window forward

• Remove 'c' at windowStart=0 → windowCharCount = {b:1, a:1}, matches = 2 (c is now undercounted)
• Add 'e' at i=3 → windowCharCount = {b:1, a:1, e:1}, matches = 2 (e doesn't match pattern)
• i=3: window size still 3, but matches = 2

Step 5: Continue sliding until end

• At i=6: window contains "bac", matches = 3, add index 4 to result
• At i=9: window contains "acd", matches = 2, no anagram found

Key insight: We maintain a sliding window of exactly pLen characters, and track character frequencies to detect when they match the pattern exactly.

Edge case handling:

• When window size exceeds pLen, we shrink from left
• When matches equals pattern length, we have found an anagram
• The algorithm correctly handles duplicate characters in both strings

The algorithm terminates because we process each character exactly twice (once when expanding, once when contracting), ensuring O(n) time complexity.

6. Java Solution

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        
        // Handle edge cases
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }
        
        // Create frequency map for pattern string p
        Map<Character, Integer> pFreq = new HashMap<>();
        for (char c : p.toCharArray()) {
            pFreq.put(c, pFreq.getOrDefault(c, 0) + 1);
        }
        
        int windowSize = p.length();
        Map<Character, Integer> windowFreq = new HashMap<>();
        
        // Initialize the first window
        for (int i = 0; i < windowSize; i++) {
            char c = s.charAt(i);
            windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);
        }
        
        // Check if first window is an anagram
        if (windowFreq.equals(pFreq)) {
            result.add(0);
        }
        
        // Slide the window through the rest of the string
        for (int i = windowSize; i < s.length(); i++) {
            // Add the new character to the window
            char newChar = s.charAt(i);
            windowFreq.put(newChar, windowFreq.getOrDefault(newChar, 0) + 1);
            
            // Remove the character that's no longer in the window
            char oldChar = s.charAt(i - windowSize);
            windowFreq.put(oldChar, windowFreq.get(oldChar) - 1);
            if (windowFreq.get(oldChar) == 0) {
                windowFreq.remove(oldChar);
            }
            
            // Check if current window is an anagram
            if (windowFreq.equals(pFreq)) {
                result.add(i - windowSize + 1);
            }
        }
        
        return result;
    }
}

This solution uses a sliding window approach with frequency maps to efficiently find all anagrams. It maintains a window of size equal to the pattern string p and compares character frequencies at each step. The key insight is that two strings are anagrams if and only if they have the same character frequencies.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the string s. We process each character at most twice - once when expanding the window and once when contracting it. The sliding window approach ensures we visit each character exactly once in the main loop.

Space Complexity: O(1). The space used by our frequency arrays is fixed at 26 characters (for lowercase English letters), which is constant regardless of input size. The auxiliary space for the result list is not counted in the space complexity analysis as it's part of the required output.

Why these bounds are correct:

• The sliding window maintains a constant-size frequency map (26 letters)
• Each character is added to and removed from the window at most once
• The isAnagram check is O(1) since we're comparing two fixed-size arrays of size 26
• The total number of operations scales linearly with input size

Optimality: This is optimal for the problem as we must examine each character at least once to determine anagrams, making O(n) the theoretical lower bound. Our solution achieves this bound with a clean sliding window approach that avoids redundant computations.

The solution is near-optimal because:

1. We avoid recomputing character frequencies from scratch at each position
2. We maintain a running window that efficiently tracks valid anagram positions
3. The fixed-size frequency arrays eliminate variable overhead from dynamic data structures

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty s: When the input string is empty, no anagrams can exist, so we return an empty list
• Empty p: When pattern string is empty, it's technically an anagram of every substring of length 0 (but this case is typically excluded in problem constraints)
• Single character strings: Both s and p are single characters - need to handle correctly

Duplicate Values and Repeated States

• Duplicate characters in pattern: The algorithm must properly count character frequencies including duplicates
• Repeated character patterns: Pattern "aab" with string "abcbaa" should find anagrams at positions 1 and 3
• Character frequency mismatches: When character counts don't match exactly, we must correctly reset and restart the sliding window

Boundary Conditions

• Pattern longer than string: If p.length() > s.length(), return empty list immediately
• Exact match: When pattern length equals string length, check if entire string is an anagram
• Single character pattern: Pattern of length 1 with multiple occurrences in string

Common Implementation Mistakes

• Incorrect window size: Not maintaining the exact pattern length window for sliding window approach
• Character frequency mismatch: Not properly updating character counts when sliding the window - forgetting to decrement or increment counts correctly
• Array bounds issues: Accessing character array indices beyond valid range when using character-to-index mapping
• Not handling character frequency differences: When a character count becomes negative or positive, not properly managing the window state
• Missing edge case handling: Not checking for null inputs or empty strings before processing

Example of Common Pitfall

// WRONG: Not properly decrementing character counts when sliding window
if (windowStart > patternLength) {
    char leftChar = s.charAt(windowStart - patternLength);
    // Missing: freq[leftChar]++ to restore count
}

The key is ensuring that character frequency tracking maintains exact balance as the window slides, which requires careful handling of both character additions and removals from the current window.

9. Alternative Approaches

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

1. Sliding Window with Character Frequency Maps Instead of using a fixed-size window, we can maintain character frequency maps for both the pattern and current window. This approach uses two HashMaps to track character counts, allowing us to compare frequency distributions directly. The time complexity remains O(n) but with higher constant factors due to hash map operations.

2. Sorting-Based Approach We could sort the pattern string and for each window, sort the substring and compare it with the sorted pattern. This would be O(n * k log k) where n is string length and k is pattern length, making it less efficient than our sliding window approach.

3. Prime Product Approach Assign unique prime numbers to each character and compute the product of primes for pattern and each window. Anagrams would have equal products. However, this approach has integer overflow issues with longer strings and requires pre-computed prime mappings.

4. Multiset-Based Approach Using a multiset (or TreeMap) to maintain character frequencies in the window. This provides O(log k) operations for insertions/deletions but increases overall complexity to O(n log k).

Our chosen sliding window with array-based frequency counting is optimal because it:

• Uses constant space for character frequency tracking (26 letters)
• Has linear time complexity O(n)
• Avoids expensive hash operations or sorting
• Is simpler to implement and debug

The array-based approach is preferred for its clean implementation, predictable performance characteristics, and optimal complexity bounds.

10. Test Cases

public class FindAllAnagramsInString {
    public List<Integer> findAnagrams(String s, String p) {
        // Implementation here
    }
}

The test cases below cover various scenarios including edge cases and boundary conditions:

// Test case 1: Basic functionality - multiple anagrams
// Input: s = "cbaebabacd", p = "abc"
// Expected: [0, 6]
// Explanation: Anagrams at indices 0 ("cba") and 6 ("bac")

// Test case 2: Single anagram
// Input: s = "abab", p = "ab"
// Expected: [0, 2]
// Explanation: Anagrams at indices 0 ("ab") and 2 ("ab")

// Test case 3: Empty pattern string
// Input: s = "abc", p = ""
// Expected: []
// Explanation: Empty pattern should return empty list

// Test case 4: Pattern longer than string
// Input: s = "ab", p = "abc"
// Expected: []
// Explanation: Pattern cannot fit in string

// Test case 5: Single character pattern
// Input: s = "aaa", p = "a"
// Expected: [0, 1, 2]
// Explanation: All positions match single character pattern

// Test case 6: No anagrams
// Input: s = "abcdef", p = "xyz"
// Expected: []
// Explanation: No matching anagrams

// Test case 7: All positions are anagrams (repeated pattern)
// Input: s = "abababab", p = "ab"
// Expected: [0, 2, 4, 6]
// Explanation: Every even index forms valid anagram

// Test case 8: Large input with many matches
// Input: s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz", p = "abc"
// Expected: [0, 1, 2, ...]
// Explanation: Multiple anagrams at consecutive positions

// Test case 9: Case sensitivity
// Input: s = "AaBbCc", p = "bCc"
// Expected: [2]
// Explanation: Only exact case match counts as anagram

// Test case 10: Unicode characters (if supported)
// Input: s = "aαβγ", p = "αβγ"
// Expected: [1]
// Explanation: Unicode characters handled correctly

These test cases ensure comprehensive coverage of:

• Basic functionality with multiple anagrams
• Edge cases like empty inputs and boundary conditions
• Pattern length constraints (longer than string)
• Single character patterns
• Non-matching scenarios
• Repeated patterns and character frequencies
• Case sensitivity requirements

11. Final Summary

The core insight is to use a sliding window approach with character frequency counting to efficiently detect all anagrams of a pattern string within a target string. By maintaining a fixed-size window that matches the pattern length and comparing character frequencies, we achieve optimal O(n) time complexity where n is the length of the target string. This solution works because anagrams must have identical character counts, and the sliding window technique allows us to process each character only once while maintaining the necessary invariants for comparison. The approach is both time and space optimal, using only O(1) extra space due to the fixed 26-character alphabet constraint.