PREP51 Editorial

editorial
1

Problem Explanation

You are given two strings S and T. You have to find the shortest substring in the string S, that has all the characters in the string T in any order.

Approach

We can use a sliding window approach maintaining the frequency of characters in the string T and the frequency of characters in the window in an unordered map. We can update the minimum length of the substring if the frequency of of the characters in the window is more than or equal to the frequency of characters in the string T.

Algorithm

Create a map tmp for and store the frequency of characters in the string T in it. Maintain a count for the number of matching characters in the two strings, a minLength for the minimum length of the substring needed and minLeft to calculate the minLength at every iteration.

  • Iterate through the string:
    • If the current character is not in the string T, skip to the next iteration.
    • Increment the freq of current character in the map
    • If freq of current character in the string S till now is less than equal to the freq of the current character in the string T → increment count denoting the count the number of matching characters
    • If count == size of T (all characters of T matched)
      • While we have extra characters:
        • Decrease freq if needed
        • left++
      • If(right-left+1<minlength):
        • minlength = new length
        • minLeft = left