Find All Anagrams in a String medium

Problem Statement

Given two strings s and p, return an array of 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, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Steps and Explanation

The core idea is to use a sliding window approach and character frequency counting. We maintain a frequency map (using a HashMap in Java) for the characters in the pattern p. Then, we slide a window of the same size as p across the string s. For each window, we compare its character frequencies with those of p. If they match, we've found an anagram.

1. Create Frequency Map for p: Count the occurrences of each character in p and store them in a HashMap.

2. Sliding Window: Initialize a sliding window of size p.length() at the beginning of s.

3. Frequency Map for Window: Create a frequency map for the current window in s.

4. Comparison: Compare the frequency maps of the window and p. If they are identical, add the start index of the window to the result list.

5. Slide the Window: Move the window one position to the right. Update the frequency map by subtracting the frequency of the character leaving the window and adding the frequency of the character entering the window.

6. Repeat: Continue steps 3-5 until the window reaches the end of s.

Code (Java)

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

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

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

        Map<Character, Integer> windowFreq = new HashMap<>();
        int windowStart = 0;
        int windowEnd = 0;

        while (windowEnd < s.length()) {
            char c = s.charAt(windowEnd);
            windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);

            if (windowEnd - windowStart + 1 == p.length()) {
                if (windowFreq.equals(pFreq)) {
                    result.add(windowStart);
                }

                char leftChar = s.charAt(windowStart);
                windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);
                if (windowFreq.get(leftChar) == 0) {
                    windowFreq.remove(leftChar);
                }
                windowStart++;
            }
            windowEnd++;
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of string s. We iterate through s once using the sliding window. HashMap operations (get, put) are on average O(1).

• Space Complexity: O(1). The HashMaps store character frequencies; the size of the HashMaps is bounded by the size of the alphabet (26 for lowercase English letters), which is a constant. The result list can at most contain n elements in the worst case. However, space complexity is still considered O(1) because it is not dependent on the input size.