Find All Anagrams in a String
Problem Description
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.
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".
Constraints:
- 1 <= s.length, p.length <= 3 * 104
sandpconsist of lowercase English letters.
Solve it on LeetCode
Approaches
1. Sliding Window with Two Hash Maps
Intuition:
The problem of finding all anagrams can be interpreted as finding all starting indices of substrings in s that are permutations of p. One direct way to approach this problem is by using a sliding window technique with the help of hash maps (or frequency arrays) to count character occurrences.
The idea is to maintain two frequency maps:
- One for the characters in the string
p. - Another for characters in the current window of
swith the same length asp.
By sliding the window across s, we compare the frequency of characters in the current window to those in p. If they match, then the start index of this window is an anagram's starting point.
Code:
- Time Complexity: O(n + m), where n is the length of
sand m is the length ofp. We have to scan both strings completely. - Space Complexity: O(1), as the size of the frequency map is constrained by the number of distinct characters (which is fixed at 26 for lowercase English letters).
2. Sliding Window with Single Array
Intuition:
By utilizing a fixed-size frequency count array instead of hash maps, we can reduce the constant factors in our solution. Since we're dealing only with lowercase English letters, we can use arrays of size 26 to store frequencies.
The idea remains the same as above: maintain a sliding window of length p across the string s, but instead of using two hash maps, use two arrays to track the frequencies. This not only brings clarity but also slightly optimizes access and modification times since operations on arrays are generally faster than on hash maps.
Code:
- Time Complexity: O(n + m), as we are still looping through both strings in their entirety.
- Space Complexity: O(1), due to the constant size of the frequency count arrays (26 elements each).