Find All Anagrams in a String - Python Solution

1. Introduction

"Find All Anagrams in a String" is a classic problem in the realm of string processing and search algorithms. It involves identifying all the start indices of a string's anagrams within another string. This problem is a great example of applying sliding window techniques and character frequency counting in string analysis.

Problem

Given a string s and a non-empty string p, the task is to find all the start indices of p's anagrams in s. The order of output does not matter. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

2. Solution Steps

1. Create a character frequency counter for the string p.

2. Initialize two pointers for the sliding window on the string s.

3. Use a hash map to keep track of the character counts in the current window.

4. Slide the window across the string s, updating the character counts.

5. When the window size equals the length of p, check if the character counts match.

6. If they match, add the start index of the window to the result list.

7. Continue sliding the window and updating the results until the end of s.

8. Return the list of starting indices.

3. Code Program

def findAnagrams(s, p):
    if len(p) > len(s):
        return []

    result = []
    pCount, sCount = [0] * 26, [0] * 26

    for i in range(len(p)):
        pCount[ord(p[i]) - ord('a')] += 1
        sCount[ord(s[i]) - ord('a')] += 1

    for i in range(len(p), len(s)):
        if pCount == sCount:
            result.append(i - len(p))

        sCount[ord(s[i]) - ord('a')] += 1
        sCount[ord(s[i - len(p)]) - ord('a')] -= 1

    if pCount == sCount:
        result.append(len(s) - len(p))

    return result

# Example Usage
print(findAnagrams("cbaebabacd", "abc"))  # Output: [0, 6]
print(findAnagrams("abab", "ab"))        # Output: [0, 1, 2]

Output:

[0, 6]
[0, 1, 2]

Explanation:

1. Character Frequency Counters: Utilizes arrays to count occurrences of each letter.

2. Sliding Window Technique: Moves a window across s to check for anagrams of p.

3. Efficient Comparison: Compares character counts instead of strings for efficiency.

4. Window Resizing: Adjusts the window size and updates counts as it moves.

5. Result Accumulation: Adds indices to the result when an anagram is found.

6. Time Complexity: Achieves O(n) time complexity where n is the length of s.

7. Practical Application: Useful in data analysis, cryptography, and pattern recognition where anagram detection is needed.