educative.io

Is shrinking the window when a character not in the pattern alphabet necessary?

Courses
,
#1

In the provided solution , we are shrinking the window when we find a character that is not found in the pattern alphabet.

// Shrink the sliding window
if (windowEnd >= pattern.length - 1) {
  leftChar = str[windowStart];
  windowStart += 1;
  if (leftChar in charFrequency) {
    if (charFrequency[leftChar] === 0) {
      matched -= 1;
    }
    charFrequency[leftChar] += 1;
  }
}
  }

This implies to me that we have to remove all the characters in the current window on the next k iterations where k is the size of the window. My question is, would it be possible to just move the window past the current character and start it again. This would how ever require a different approach to tracking the characters in the window. In my solution I used another hashmap which I would update as characters are found. I would “reset” that map when a string character not in the pattern is found. This implies more storage but I think the solution still has the same complexity for space.

Do these solutions differ that much? Is one approach recommended vs the other?

2 Likes
#2

Technically we are shrinking the window with the 3rd line
windowStart += 1

So we shrink (or slide the window as I prefer to think of it in this case) so that it’s always equal to the length of the pattern regardless if the character is present in charFrequency or not