Reg :- minimum window string

#1

Sir before entering if(count==PL)

the FS would be {e:1 ,a:1 , f:1 ,b:1 ,c:1 , g:1}
this array would make count==PL
but the while loop wont work
it doesnt satisfy any condition given in while loop

#2

Hi, your doubt is not clear to me. Do you want me to debug your code or something?

#3

Nope sir dry run for a single test case

#4

Please be patient while I type.

#5

Okay, let’s say that the testcase is

    string s=" eafbcgdefg";
    string p="efg";

Therefore, FP[‘e’] = FP[‘f’] = F[‘g’] = 1 and rest all are 0.

now, for i = 0,
ch = ’ ’ (space)
as FP[ch] = 0, count does not update and is still 0.
now count is != PL, therefore the if block is not executed.

for i = 1, ch = ‘e’, therefore count increments to 1, and if block is still no executed.

for i = 2, ch = ‘a’, but FP[ch] = 0, so nothing happens

for i = 3, ch = ‘f’, count increments to 2

for i = 4 and 5, nothing happens

for i = 6, ch = ‘g’, count increments to 3,
also count == PL, therefore we execute the if block now,
start = 0
what the while loop does is to increase the start as long as the characters are contained,
as s[start] is useless and can be discarded, we increment start to 1
now, s[start] = s[1] = ‘e’, is required so we can’t proceed any further and the loop ends.

Now, we compare the answers with int window_len = i-start+1;, if smaller we update the answer and so on.

#6

so why it is giving efg as output ?
then it should give the window starting from the initial index

#7

Because, I didn’t dry run till the end, where there is ‘efg’.

Do you want me to dry run for that part as well?

#8

yes sir please dry run for the output efg !

#9

now for i = 7, ch = ‘d’, nothing happens to count (it is still = 3)
we go into the if block, and start = 1,
therefore temp = s[start] = ‘e’, the while condition

while( FP[temp]==0 || FS[temp]>FP[temp])

is not satisfied for this and the loop therefore never runs.

i = 8, ch = ‘e’, FS[‘e’] becomes 2 now, the count still remains the same (= 3),
we go into if block, and start = 1,

  1. and temp = ‘e’, FS[‘e’] = 2 and FP[‘e’] = 1, therefore the while loop runs
    after one iteration, FS[‘e’] = 1, start = 2, temp = s[start] = s[2] = ‘a’,
  2. temp = ‘a’, FP[‘a’] = 0, therefore the condition is again satisfied
    after this iteration, FS[‘a’] = 0, start = 3, temp = s[start] = s[3] = ‘f’,
  3. temp = ‘f’, FS[‘f’] = 1, therefore the condition is not satisfied and the loop ends.

for i = 9, ch = ‘f’, … (try to dry run from here, because it is the final part and it will be beneficial if you try this on your own)

If you still can’t do it, reach back to me, I’ll be happy to help.

#10

thank you so much understood , i thought count is npot decrememnting how it is handled is now known .

1 Like