Given two strings s and p, return the list of every starting index in s where a substring begins that is an anagram (a rearrangement) of p. Return the indices in increasing order.
Example 1
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
"cba" starts at 0 and "bac" starts at 6.Example 2
Input: s = "abab", p = "ab"
Output: [0,1,2]
"ab", "ba" and "ab" start at 0, 1 and 2.Constraints
- 1 <= s.length, p.length <= 3 * 10^4
- Both strings contain only lowercase English letters
Hints
Frequently asked at: Amazon, Meta, Microsoft, Paytm
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting or counting every window of length m = len(p) from scratch costs O(n * m). Neighbouring windows differ by just two letters, so keep one count array for the window and update it in O(1) as it slides. Comparing two arrays of 26 counts is constant time, so every start index is checked in O(1).
Algorithm
- If
len(p) > len(s), return an empty list. - Count the letters of
pintoneed. - For each index
iins, adds[i]towindow; ifi >= m, removes[i - m]. - When
i >= m - 1andwindow == need, record the starti - m + 1. - Return the recorded indices.
Time:
O(26 * n), which is O(n)Space: O(1), two arrays of 26Interview tip: This is the same idea as Permutation in String; the only difference is collecting every match instead of stopping at the first. Mention that you would reuse the "matches count" refinement to drop the 26 factor.
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: n, m = len(s), len(p) res = [] if m > n: return res need = [0] * 26 window = [0] * 26 for c in p: need[ord(c) - 97] += 1 for i in range(n): window[ord(s[i]) - 97] += 1 # letter entering if i >= m: window[ord(s[i - m]) - 97] -= 1 # letter leaving if i >= m - 1 and window == need: res.append(i - m + 1) return resCtrl + Enter runs the examples