No idea is clicking how to do it with hashing

#1

plz… give some hint

#2

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 the only occurrence 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 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.

#3

oooo… it’s similar to sliding window technique but with a little restrictions…on character frequency

#4


check the code … 7 test cases passed but 3 failed

#5

You can refer this