Code Implementation

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str):
        res = []
        p_count = Counter(p)
        s_count = Counter()
        p_len = len(p)
        
        for i in range(len(s)):
            s_count[s[i]] += 1
            if i >= p_len:
                if s_count[s[i - p_len]] == 1:
                    del s_count[s[i - p_len]]
                else:
                    s_count[s[i - p_len]] -= 1
            if s_count == p_count:
                res.append(i - p_len + 1)
        return res
      

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        vector<int> p_count(26, 0), s_count(26, 0);
        int p_len = p.size(), s_len = s.size();
        if (s_len < p_len) return res;
        for (char c : p) p_count[c - 'a']++;
        for (int i = 0; i < s_len; ++i) {
            s_count[s[i] - 'a']++;
            if (i >= p_len)
                s_count[s[i - p_len] - 'a']--;
            if (s_count == p_count)
                res.push_back(i - p_len + 1);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        int pLen = p.length(), sLen = s.length();
        if (sLen < pLen) return res;
        for (char c : p.toCharArray()) pCount[c - 'a']++;
        for (int i = 0; i < sLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            if (i >= pLen)
                sCount[s.charAt(i - pLen) - 'a']--;
            if (Arrays.equals(sCount, pCount))
                res.add(i - pLen + 1);
        }
        return res;
    }
}
      

var findAnagrams = function(s, p) {
    const res = [];
    const pCount = Array(26).fill(0);
    const sCount = Array(26).fill(0);
    const a = 'a'.charCodeAt(0);
    const pLen = p.length, sLen = s.length;
    if (sLen < pLen) return res;
    for (let i = 0; i < pLen; i++) pCount[p.charCodeAt(i) - a]++;
    for (let i = 0; i < sLen; i++) {
        sCount[s.charCodeAt(i) - a]++;
        if (i >= pLen)
            sCount[s.charCodeAt(i - pLen) - a]--;
        if (pCount.join() === sCount.join())
            res.push(i - pLen + 1);
    }
    return res;
};
      

Problem Description

Given two strings, s and p, find all the start indices of p's anagrams in s. You need to return a list of all such starting indices in s where the substring is an anagram of p. An anagram is a rearrangement of letters, so two strings are anagrams if they contain the same characters with the same frequencies.

• You must find all possible starting indices; there can be more than one.
• Each letter in s and p is a lowercase English letter.
• Indices must not be reused; each substring is considered separately.

Example: For s = "cbaebabacd" and p = "abc", the output is [0, 6] because the substrings "cba" and "bac" are anagrams of "abc".

Thought Process

The problem asks us to find all substrings of s that are anagrams of p. A brute-force approach would be to check every substring of length len(p) in s and verify if it's an anagram. However, this is inefficient because it involves sorting or counting characters for every possible substring, leading to high time complexity.

Upon reflection, we realize that an anagram is fully determined by the counts of each character. Instead of checking each substring from scratch, we can keep track of the character counts as we move through s using a sliding window. This way, we only update the counts for the characters entering and leaving the window, making the process much more efficient.

The key insight is to use a fixed-size window (the length of p) and compare the character counts in this window with those in p. If they match, we've found an anagram.

Solution Approach

To solve this problem efficiently, we use the sliding window technique combined with character counting. Here are the steps:

1. Count Characters in p:
   • Create a hash map or array to store the frequency of each character in p.
2. Initialize the Sliding Window:
   • Use another hash map or array to store the frequency of characters in the current window of s (of length len(p)).
3. Slide the Window:
   • Iterate over s. For each character, add it to the window count.
   • If the window size exceeds len(p), remove the leftmost character from the window count.
   • After each move, compare the window count with the p count. If they match, record the starting index.
4. Return the Result:
   • After iterating through s, return the list of starting indices where anagrams were found.

We use arrays of size 26 (for lowercase English letters) or hash maps for counting, allowing constant time updates and comparisons.

Example Walkthrough

Let's use s = "cbaebabacd" and p = "abc".

• Step 1: Count characters in p: {a:1, b:1, c:1}.
• Step 2: Start with the first window in s ("cba"):
  • Window count: {c:1, b:1, a:1} (matches p count)
  • Add index 0 to the result.
• Step 3: Move window by 1 ("bae"):
  • Remove 'c', add 'e' → window: {b:1, a:1, e:1} (not a match)
• Continue:
  • "aeb": {a:1, e:1, b:1} (not a match)
  • "eba": {e:1, b:1, a:1} (not a match)
  • "bab": {b:2, a:1} (not a match)
  • "aba": {a:2, b:1} (not a match)
  • "bac": {b:1, a:1, c:1} (matches)
  • Add index 6 to the result.
• Final result: [0, 6]

At each step, we only update the counts for the entering and leaving characters, making the process efficient.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O((n - m + 1) * m), where n is the length of s and m is the length of p. For each substring, we check if it's an anagram, which takes O(m) time.
  • Space Complexity: O(1), ignoring output, since only temporary arrays are used for counting.
• Optimized Sliding Window Approach:
  • Time Complexity: O(n), because each character is added and removed from the window exactly once, and comparing counts takes O(1) time (since the alphabet size is fixed at 26).
  • Space Complexity: O(1), since we use fixed-size arrays for counting, regardless of input size.

Summary

The problem of finding all anagrams of p in s can be solved efficiently using the sliding window technique and character counting. By updating the counts as we move the window and comparing with the target counts, we reduce time complexity from quadratic to linear. The use of fixed-size arrays or hash maps for character frequencies ensures fast lookups and updates, making the solution both elegant and efficient for large inputs.