String Window Question

#1

I have written this code https://ide.codingblocks.com/s/72850 1.
i am not able to understand how to obtain the shortest possible substring (my code is computing the largest possible substring).
Can you please explain or atleast give a hint on the approach ?

#2 
1)First check if length of string is less than the length of given pattern, if yes then "no such window can exist ".
  1. Store the occurrence of characters of given pattern in a hashtable
  2. Start matching the characters of pattern with the characters of string i.e. increment count if a character matches
  3. Check if (count == length of pattern ) this means a window is found
  4. If such window found, try to minimize it by removing extra characters from beginning of current window.
    6)Update min_length
    7)Print the minimum length window.
1 Like
#3

How to remove those extra characters ? Each character in the window is there because we added it (since it was there in s2). So if we start removing characters from the string window how do we know we wouldn’t end up removing essential characters that were present in s2.?

Find my updated code at https://ide.codingblocks.com/s/72850. The length between “start” and “end” comprises of the letters which are in s2. How to proceed further from here ?

#4

To ensure that your program won’t remove the essential characters.

  1. Store the insurance of characters you have traversed so far.

  2. Once a window is detected, try to remove the unnecessary characters from the start of that window by checking for the condition (count_of_character_string>count_of_character_pattern). i.e. there are more than required occurance of that character in the string or if there are no occurance of that character in the pattern.
    Example:
    String: anbc acdaedbe
    Pattern: debca
    Window detected: anbc acdae (it contains all the characters of pattern)

Now start removing the extra char from the start of the window.
Start=0;
Str[0]=a;
There are 3 occurance of “a” in window but only 1 in pattern.
So, this “a” can be removed.

Start++;
Str[Start]=n;
This character is not present in pattern. So, can be eliminated.

Start++;
Str[Start]=b;
b has only occurance in both. So, this won’t be removed. Hence no further removal in this window.

  1. Now look for another window in the string. Perform step 2 on it.

  2. Check if the size of new window is smaller than smallest length marked so far . If yes, make it as the smallest.

Hint: store the starting index and the length of the smallest string to reduce space requirement.

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.