educative.io

Why are we putting the character back in again

Courses
,
#1

I understood why we are checking for a match and if they reach 0 its correct. when decreasing the window size why are we putting the element back in?

if (windowEnd >= pattern.length() - 1) { // 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);

        }

      }
#2

Hi,

Match count is set against size of the MAP charFrequencyMap
Here a Key can have multiple value, example below

We put back the value in map so we can match with next window.

pattern = “abb”
String=“abcdaebaa”
here only last 3 character “baa” from String will match.

Now when we start, a window cannot have length more than pattern length==3

Here when we start we will have MAP as below
a–>1
b–>2
After processing String “abcdaebba” till index 2, ‘c’
a->0
b–>1
matched–>1
Now when we reach index 3 character d. We need to remove index = 0, character=‘a’
When we do this and don’t put back the char a, the MAP will be below
a–>0
b–>2

Now when we compare we are comparing just with b–>2 as ‘a’ will always match as its not being reset back to 1.

2 Likes
#3

Thank you for the clarification! It’s really been helpful!

Just a quick question regarding the second to the last line: why does the count of “b” go back to 2, instead of staying at 1?

Thank you~

#4

Thanks for this explanation! I was confused on why the solution was putting back the character that was going out of the window.