The challenge
Return every start index where a substring of s is an anagram of pattern. Anagrams have exactly the same character multiplicities.
Strings contain lowercase English letters. The pattern is nonempty. Indices are zero-based.
Example
s = cbaebabacd, pattern = abc → [0, 6].
Use the walkthrough below to inspect the input and each state change.
See Anagram windows, step by step
Expand, shrink, and inspect the window state.
10 elements · zero-based indicespattern = abc
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 20
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
[]
View exact input
Input: ["c","b","a","e","b","a","b","a","c","d"] · pattern = abc
Current window is empty.
Put it into code
Keep a frequency vector for a window of pattern.length characters. Comparing 26 counters is constant work for this alphabet.
Indices are zero-based. C++ uses C++17 or later.
def find_anagrams(s, pattern):
# Lowercase English letters; pattern is nonempty.
need, window = [0] * 26, [0] * 26
for char in pattern:
need[ord(char) - ord('a')] += 1
answer, k = [], len(pattern)
for right, char in enumerate(s):
window[ord(char) - ord('a')] += 1
if right >= k:
window[ord(s[right - k]) - ord('a')] -= 1
if right >= k - 1 and window == need:
answer.append(right - k + 1)
return answer#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> find_anagrams(const string& s, const string& pattern) {
array<int, 26> need{}, window{};
for (char c : pattern) ++need[c - 'a'];
int k = (int)pattern.size();
vector<int> answer;
for (int r = 0; r < (int)s.size(); ++r) {
++window[s[r] - 'a'];
if (r >= k) --window[s[r - k] - 'a'];
if (r >= k - 1 && window == need) answer.push_back(r - k + 1);
}
return answer;
}