Solution


Approach 1: Sliding Window

Intuition

The question asks us to return the minimum window from the string which has all the characters of the string . Let us call a window desirable if it has all the characters from .

We can use a simple sliding window approach to solve this problem.

In any sliding window based problem we have two pointers. One pointer whose job is to expand the current window and then we have the pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.

The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.

The answer is the smallest desirable window.

For eg. S = "ABAACBAB" T = "ABC". Then our answer window is "ACB" and shown below is one of the possible desirable windows.


Algorithm

  1. We start with two pointers, and initially pointing to the first element of the string .

  2. We use the pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of .

  3. Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.

  4. If the window is not desirable any more, we repeat onwards.

The above steps are repeated until we have looked at all the windows. The smallest window is returned.


Complexity Analysis

  • Time Complexity: where |S| and |T| represent the lengths of strings and . In the worst case we might end up visiting every element of string twice, once by left pointer and once by right pointer. represents the length of string .

  • Space Complexity: . when the window size is equal to the entire string . when has all unique characters.


Approach 2: Optimized Sliding Window

Intuition

A small improvement to the above approach can reduce the time complexity of the algorithm to , where is the string formed from S by removing all the elements not present in .

This complexity reduction is evident when .

This kind of scenario might happen when length of string is way too small than the length of string and string consists of numerous characters which are not present in .

Algorithm

We create a list called which has all the characters from string along with their indices in , but these characters should be present in .

  S = "ABCDDDDDDEEAFFBC" T = "ABC"
  filtered_S = [(0, 'A'), (1, 'B'), (2, 'C'), (11, 'A'), (14, 'B'), (15, 'C')]
  Here (0, 'A') means in string S character A is at index 0.

We can now follow our sliding window approach on the smaller string .

Complexity Analysis

  • Time Complexity : where |S| and |T| represent the lengths of strings and . The complexity is same as the previous approach. But in certain cases where <<< , the complexity would reduce because the number of iterations would be .
  • Space Complexity : .


Analysis written by: @godayaldivya.