educative.io

Permutation in a String, https://www.educative.io/courses/grokking-the-coding-interview/N0o9QnPLKNv

Courses
,
#1

Could anyone give me an example where we decrement matched variable and why we need to decrement the matched variable?

I could not get any example where it will hit this line. Even I comment the decrementing of matched line still the output is same i.e commenting this line did not alter the way the logic works at all.

  if left_char in char_frequency:
    if char_frequency[left_char] == 0:
      matched -= 1

Many thanks for your time.

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/4679331609575424

#2

Hi @learn

Firstly, the case of decrementing the matched variable is when we wish to decrease the window size – it happens when the window size exceeds the total number of characters in the pattern. Secondly, we only increase the frequency is HashMap if the dropped character is in the pattern. So, you shrink the window size, irrespective of the character being a part of the pattern or not, and then adjust the matched variable and the frequency in the HashMap, only if the dropped character is a part of the pattern.

Try implementing the logic on this example: find_permutation("odicf", "dc"). It produces different result when the code is commented out.

#3

My test case : findPermutation*(“bbcaf”,“abc”)

Query: you don’t consider the second b as matched as per your solution. why?