educative.io

Can someone explain why we only increment match count when sliding front forward

Courses
, ,
#1

I can see the solution works but I’m a bit confused why in the first part of the loop we only ever increase matched when its very possible that adding a new character to the frequency will take a previously matched character from 0 to - 1 which should decrement matched by 1.

const rightChar = str[windowEnd];
if (rightChar in charFrequency) {
  // Decrement the frequency of matched character
  charFrequency[rightChar] -= 1;
  if (charFrequency[rightChar] === 0) {
    matched += 1;
  }
}

I would think we would need to handle both creating a new match and un-matching a character but when I modify the code to take that into account I start getting failing tests. My brain just can’t wrap itself around why this solution works when the matched count is sometimes out of sync with the character counts. Hope someone can help me understand why this work.

Thank you

#2

Hello @Colin_Chauche
Thank you for reaching out to us. In this problem, we have decremented matched and incremented char_frequency in second part of the for loop. If we do not find pattern (e.g ‘abc’ of length 3) in string (‘oidbcaf’) in first 3 iterations then we will move to next part of for loop which is

    if window_end >= len(pattern) - 1:
      left_char = str1[window_start]
      print("window_end",window_end, "window_start",window_start,"left_char",left_char)
      window_start += 1
      if left_char in char_frequency:
        if char_frequency[left_char] == 0:
          matched -= 1
        char_frequency[left_char] += 1

here we are incrementing the frequency of that specific character in char_frequency and decrementing the match by 1.