Problem
Given two strings s and p, return the starting indices of all anagrams of p in s. The returned indices may be in any order.Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "cbaebabacd"
p = "abc"
Output
[0,6]
Solution
This solution uses the Sliding Window technique along with two frequency arrays.One array stores the character frequencies of the pattern p, while the other stores the frequencies of the current window in s.
The window size is always equal to the length of p.
As the window slides through the string, the frequency of the newly added character is incremented, and the frequency of the removed character is decremented.
Whenever the two frequency arrays are equal, the current window is an anagram of p, and its starting index is added to the result.
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) {
return result;
}
int[] target = new int[26];
int[] window = new int[26];
for (char c : p.toCharArray()) {
target[c - 'a']++;
}
int windowSize = p.length();
for (int right = 0; right < s.length(); right++) {
window[s.charAt(right) - 'a']++;
if (right >= windowSize) {
window[s.charAt(right - windowSize) - 'a']--;
}
if (Arrays.equals(target, window)) {
result.add(right - windowSize + 1);
}
}
return result;
}
Complexity
The algorithm processes each character of the string exactly once while maintaining a fixed-size sliding window.Comparing the two frequency arrays takes constant time because they each contain only 26 elements. Therefore, the overall time complexity is
O(n). The two frequency arrays have a fixed size of 26, so the extra space complexity is
O(1).
