The challenge
Return true if any substring of s is a permutation of pattern; otherwise return false.
Strings contain lowercase English letters. The pattern is nonempty. Indices are zero-based.
Example
s = eidbaooo, pattern = ab → true, because ba appears at index 3.
Use the walkthrough below to inspect the input and each state change.
See Permutation check, step by step
Expand, shrink, and inspect the window state.
8 elements · zero-based indicespattern = ab
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 11
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
false
View exact input
Input: ["e","i","d","b","a","o","o","o"] · pattern = ab
Current window is empty.
Put it into code
Use the anagram frequency window, returning immediately at the first match. The function takes the source first and pattern second.
Indices are zero-based. C++ uses C++17 or later.
def contains_permutation(s, pattern):
# Lowercase English letters; pattern is nonempty.
need, window = [0] * 26, [0] * 26
for char in pattern:
need[ord(char) - ord('a')] += 1
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:
return True
return False#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
bool contains_permutation(const string& s, const string& pattern) {
array<int, 26> need{}, window{};
for (char c : pattern) ++need[c - 'a'];
int k = (int)pattern.size();
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) return true;
}
return false;
}