Find All Anagrams in a String - Python Solution

1. Introduction

"Find All Anagrams in a String" is a string processing challenge that involves finding all the start indices of anagrams of one string within another. This problem tests the ability to efficiently search for permutations within a larger string, utilizing concepts like hash tables and the sliding window technique.

Problem

Given two strings s (the source string) and p (the target string), the task is to find all the start indices of p's anagrams within s. The answer may be returned in any order. An anagram is defined as a rearrangement of the characters of one string to form another string, using all original characters exactly once.

2. Solution Steps

1. Create a hash table to store the frequency of each character in p.

2. Use a sliding window of length equal to p to traverse s.

3. Move the window across s, keeping track of the frequency of characters in the current window.

4. When the character frequency in the window matches that of p, add the start index of the window to the result.

5. Continue this process until the end of s is reached.

6. Return the list of starting indices where anagrams of p were found in s.

3. Code Program

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() == 0 || p.length() == 0 || s.length() < p.length()) {
            return result;
        }

        HashMap<Character, Integer> pCount = new HashMap<>();
        for (char c : p.toCharArray()) {
            pCount.put(c, pCount.getOrDefault(c, 0) + 1);
        }

        int start = 0, end = 0, len = p.length(), diff = len;
        for (end = 0; end < len; end++) {
            char temp = s.charAt(end);
            if (pCount.containsKey(temp)) {
                pCount.put(temp, pCount.get(temp) - 1);
                if (pCount.get(temp) >= 0) {
                    diff--;
                }
            }
        }

        if (diff == 0) {
            result.add(0);
        }

        while (end < s.length()) {
            char startChar = s.charAt(start++);
            if (pCount.containsKey(startChar)) {
                if (pCount.get(startChar) == 0) {
                    diff++;
                }
                pCount.put(startChar, pCount.get(startChar) + 1);
            }

            char endChar = s.charAt(end++);
            if (pCount.containsKey(endChar)) {
                pCount.put(endChar, pCount.get(endChar) - 1);
                if (pCount.get(endChar) >= 0) {
                    diff--;
                }
            }

            if (diff == 0) {
                result.add(start);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findAnagrams("cbaebabacd", "abc")); // Output: [0, 6]
        System.out.println(solution.findAnagrams("abab", "ab"));        // Output: [0, 1, 2]
    }
}

Output:

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

Explanation:

1. Character Frequency: The frequency of each character in p is stored in a hash table.

2. Sliding Window: A sliding window of length equal to p is used to traverse s.

3. Window Expansion and Contraction: The window expands and contracts, keeping track of character frequencies within it.

4. Anagram Detection: When the character frequencies in the window match those in p, the start index of the window is added to the result.

5. Efficient Iteration: The window slides through s efficiently, ensuring an O(n) time complexity.

6. Result: The function returns a list of start indices where anagrams of p are found in s.

7. Java Implementation: The solution is implemented in Java, showcasing efficient use of data structures like HashMap and ArrayList.