Technical Interview Question

You are given two strings, s and p, return all the start indices of p's anagrams in s. You may return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Function signature: List[int] findAnagrams(String s, String p)

Input:

• String s representing the main string (1 <= s.length <= 3 * 10^4)
• String p representing the string which is a possible anagram of some substring of s (1 <= p.length <= s.length)

Output:

• A list [a1, a2, ...] containing the starting indices of p's anagrams in s.

Answer

To solve this problem efficiently, we can use the sliding window technique.

1. Initialize an empty list result to store the starting indices of the anagrams.
2. Create two arrays, sCount and pCount, of size 26 to represent the count of letters in s and p respectively. Initialize all the elements of both arrays with 0.
3. Count the frequency of each letter in string p and update the pCount array accordingly.
4. Initialize two pointers, left and right, both pointing to the starting position of string s.
5. Start a loop until the right pointer reaches the end of string s.
6. Increment the frequency of the letter at the right position in string s by 1 in sCount array.
7. If the difference between the right and left pointers is equal to the length of string p, then we have a potential anagram.
8. In that case, compare the sCount and pCount arrays. If they are equal, then the current substring from left to right is an anagram of string p. Append the left pointer to the result list.
9. Decrement the frequency of the letter at the left position in string s by 1 in sCount array.
10. Move the left pointer one step forward.
11. Move the right pointer one step forward.
12. Finally, return the result list containing the starting indices of p's anagrams in s.

Let's implement this solution in Python: