In the solution the condition is:
if window_end >= len(pattern) - 1:
Shouldn’t it be:
window_end - window_start + 1 > len(pattern)
That would satisfy condition 5) If the window size is greater than the length of the pattern, shrink the window to make it equal to the pattern’s size.
I had the same thought and then I figured it out -
If window_end is greater than or equal to the length of the pattern, then we ALWAYS have to slide the window, since the window must always be the length of the pattern.
Also if we do it with your suggested condition, then this test fails:
find_permutation(odicf, dc)
Thanks for the explanation Steve.
//the code below shows that we are ready to move the window when it is exactly
// of the pattern.length(); before windowEnd++ we want to process the outgoing element. Everything //else is confusing.
bool SlidingWindow::PermutationExists(const string& str, const string& pattern) {`
unordered_map<char, int> frequencies;
for(char ch: pattern) {
frequencies[ch]++;
}
int windowStart = 0;
int matchCount = 0;
for(int windowEnd = 0; windowEnd < int(str.size()); windowEnd++) {
if(frequencies.find(str[windowEnd]) != frequencies.end()) {
frequencies[str[windowEnd]]--;
if(frequencies[str[windowEnd]] == 0) {
matchCount++;
}
}
if(matchCount == (int)frequencies.size()) {
return true;
}
if(windowEnd - windowStart + 1 == int(pattern.length())) {
if(frequencies.find(str[windowStart]) != frequencies.end()) {
if(frequencies[str[windowStart]] == 0) {
matchCount--;
}
frequencies[str[windowStart]]++;
}
windowStart++;
}
}
return false;
}