String Window Question

#1

How to solve this problem Please tell me correct approach

#2

Hello @dsingh200021,

Approach:

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

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 the required occurrence of that character in the string or if there is no occurrence 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 the pattern. So, can be eliminated.

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

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

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

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

Hope, this would help.
Give a like if you are satisfied.

#3

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.