Programming interview questions

Looking for good programming/interview questions?

Use the search below to find our solutions for selected questions!

Minimum window substring challenge

Sharing is caring!

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity \mathcal{O}(n).

Sample Input 0

Sample Output 0

Solution
The first step we are going to take is, count the occurrences of each letter in string T. We will use a Map for that.

We then iterate over each character of string S using an iterator i and keep a count of characters encountered so far. Again, for that we will use a Map<Character, Integer> count. We will track the start and ending of the smallest substring using start and end. At first both, start and end are initialised to -1. As soon, as we hit a character that is contained in T we set start = i, as this is the soonest possible way that a substring may contain all characters in T.

While we are iterating over the letters in S, we check if we have collected all the required characters. As soon as that is the case, we set end = i. Now we have a substring that contains all the characters of T. But we are not done yet. Maybe there exists a smaller substring that also contains all the characters of T.

We continue iterating over the remaining characters in S while incrementing our end to i and adding them to count. If we hit a character that is equal to S[start] (the tail of the current substring) we remove it from the current substring. We also keep removing characters from the tail that are not contained in T or characters that are in T but we have in excess.

When we are done removing characters, we check if the new resulting substring is shorter than the previous one. If such is the case we update our answer.

The algorithm terminates when we have iterated over all characters in S.

The full implementations (two variations) are listed below.

Full code (Implementation 1)

Full code (Implementation 2)