The line of code is:
if (windowEnd >= pattern.length() - 1) { // shrink the window by one character
But should the length of the window be windowEnd - windowStart + 1 (instead of windowEnd here)？
its checking if the windowEnd is at the pattern size. (only when it reaches certain size then you can check the pattern match). window resizing is done also once the windowEnd reaches that certain size.
Same, I too got confused
The text says "If the window size is greater than the length of the pattern, shrink the window to make it equal to the size of the pattern."
In code, I would translate it to
windowEnd - windowStart + 1 > pattern.length()
We have been using “window size” to be “windowEnd - windowStart + 1” consistently.
I do not know for this question why was it done like
(windowEnd >= pattern.length() - 1) on line 24 ... looks like a hack.
Why will “windowStart” NOT participate in deciding the “window size”?
Ok, for the interest of others, I have figured out the better approach
Basically, when the window size is equal to the pattern size, shrink the window by 1 by increasing start by 1.
import java.util.*;
class StringPermutation {
public static boolean findPermutation(String str, String pattern)
{
int windowStart = 0, matched = 0;
Map<Character, Integer> charFrequencyMap = new HashMap<>();
for (char chr : pattern.toCharArray())
charFrequencyMap.put(chr, charFrequencyMap.getOrDefault(chr, 0) + 1);
// our goal is to match all the characters from the 'charFrequencyMap' with the current window
// try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++)
{
char rightChar = str.charAt(windowEnd);
if (charFrequencyMap.containsKey(rightChar))
{
// decrement the frequency of the matched character
charFrequencyMap.put(rightChar, charFrequencyMap.get(rightChar) - 1);
if (charFrequencyMap.get(rightChar) == 0) // character is completely matched
matched++;
}
if (matched == charFrequencyMap.size()) return true;
if (windowEnd - windowStart + 1 == pattern.length())
{ // shrink the window by one character
char leftChar = str.charAt(windowStart++);
if (charFrequencyMap.containsKey(leftChar))
{
if (charFrequencyMap.get(leftChar) == 0)
matched--; // before putting the character back, decrement the matched count
// put the character back for matching
charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) + 1);
}
}
}
return false;
}
public static void main(String[] args) {
System.out.println("Permutation exist: " + StringPermutation.findPermutation("oidbcaf", "abc"));
System.out.println("Permutation exist: " + StringPermutation.findPermutation("odicf", "dc"));
System.out.println("Permutation exist: " + StringPermutation.findPermutation("bcdxabcdy", "bcdyabcdx"));
System.out.println("Permutation exist: " + StringPermutation.findPermutation("aaacb", "abc"));
System.out.println("Permutation exist: " + StringPermutation.findPermutation("dfakb", "ab"));
}
}Hello!
You wrote
" The text says "If the window size is GREATER THAN the length of the pattern, shrink the window to make it equal to the size of the pattern."
In code, I would translate it to
windowEnd - windowStart + 1 > pattern.length() "
Why in your code you write if (windowEnd - windowStart + 1 == pattern.length()) ?
@Dmitry3 Can you please paste a link to the question you are talking about?
For the following line:
if (windowEnd >= pattern.length() - 1) { // shrink the window by one character
As soon as windowEnd equals the length of the pattern, we start decrementing the length of the window by one in each iteration. This means that window size will never be more than the length of the pattern. This is why we don’t need a check like:
windowEnd - windowStart + 1
Having said this, you can still use this check, it will work too.
This doesn’t make sense… the windowEnd is only equal to the length of window when start = 0, so in other cases we would need to check windowEnd - windowStart + 1 to compare the pattern length to the length of the window. we don’t need to decrement the length of the window if the end is an index > pattern length but the window length is less than the pattern length.
Try dry-running the code to see how things are working.
Hey Design Guru, I tried to do the dry run: Can you find out the problem with this?
bool SlidingWindow::PermutationExists(const string& str, const string& pattern) {
unordered_map<char, int> mappings;
for(char ch: pattern) {
mappings[ch]++;
}
int windowStart = 0;
int matchCount = 0;
for(int windowEnd = 0; windowEnd < int(str.size()); windowEnd++) {
char leftChar = str[windowEnd];
if(mappings.find(leftChar) != mappings.end()) {
mappings[leftChar]--;
if(mappings[leftChar] == 0) {
matchCount++;
}
}
if(matchCount == (int)mappings.size()) {
// cout << "Current MatchCount: " << matchCount << endl;
// cout << "Matchfound" << endl;
return true;
}
if(windowEnd - windowStart + 1 > int(pattern.length())) {
if(mappings.find(str[windowStart]) != mappings.end()) {
matchCount--;
mappings[str[windowStart]]++;
}
windowStart++;
}
}
return false;
}