Find all Anagrams in a String

Problem Link

Find All Anagrams in a String – LeetCode #438

Problem Statement

You are given two strings s and p.

Your task is to return a list of all the start indices in s where the substring is an anagram of p.

You can return the result in any order.

Examples

• Input: s = "cbaebabacd", p = "abc"
  Output: [0, 6]
  Explanation: Anagrams "cba" and "bac" found at indices 0 and 6.

• Input: s = "abab", p = "ab"
  Output: [0, 1, 2]
  Explanation: Anagrams "ab", "ba", "ab" found at indices 0, 1, and 2.

Constraints

• 1 <= s.length, p.length <= 3 × 10⁴

• Both s and p consist of lowercase English letters only

Intuition

We need to identify all substrings in s of length equal to p.length() that are anagrams of p.

This can be seen as a fixed-size sliding window + frequency map comparison problem:

• An anagram has the same character counts as the original word.

• So we can use frequency counting arrays of size 26 (for lowercase letters) to compare substrings in constant time.

• Instead of comparing full arrays every time, we can maintain a sliding difference of counts by adjusting the frequency map as the window slides.

Approach

1. Create a frequency array counter of size 26 and initialize it with character frequencies from p.

2. Use two pointers i and j to define the sliding window of length k = p.length() over string s.

3. For every character entering the window (s[j]), decrement its count from counter.

4. When window size reaches k:

   • Check if all values in counter are 0 (indicating an anagram).

   • If yes, add i (start index of window) to result list.

   • Before moving i forward, restore the character going out (s[i]) by incrementing its count in counter.

5. Move the window forward and repeat.

Java Code

class Solution {
    private boolean allZero(int[] counter) {
        for (int num : counter) {
            if (num != 0) return false;
        }
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int k = p.length();
        List<Integer> result = new ArrayList<>();
        if (n < k) return result;

        int[] counter = new int[26];

        // Step 1: Count frequencies of characters in p
        for (char ch : p.toCharArray()) {
            counter[ch - 'a']++;
        }

        // Step 2: Sliding window over s
        int i = 0, j = 0;
        while (j < n) {
            counter[s.charAt(j) - 'a']--;

            if (j - i + 1 == k) {
                if (allZero(counter)) {
                    result.add(i);
                }

                // Slide the window
                counter[s.charAt(i) - 'a']++;
                i++;
            }

            j++;
        }

        return result;
    }
}

Time and Space Complexity

• Time Complexity: O(n * 26) = O(n)
  Each window check takes O(26) time (constant), and we slide the window over n characters.

• Space Complexity: O(1)
  Fixed-size array of 26 letters is used.

Dry Run

Input:

s = "cbaebabacd", p = "abc"

Step-by-step:

• Initial counter for p: {'a':1, 'b':1, 'c':1}

• Slide window of size 3:

  • Substring "cba" → matched → add 0

  • "bae" → no match

  • "aeb" → no match

  • "eba" → no match

  • "bab" → no match

  • "aba" → no match

  • "bac" → matched → add 6

Output: [0, 6]

Conclusion

This problem is a textbook example of the Fixed-Size Sliding Window + Hash Table Lookup pattern:

• The window size is fixed to p.length()

• Instead of comparing substrings directly, we compare frequency signatures

• The sliding window is optimized by incrementally adjusting character counts

This approach generalizes well to:

• Permutation matching

• Substring comparison

• Frequency-based matching patterns