LeetCode Q76: Minimum Window Substring (hard*)

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

For example,

S = "ADOBECODEBANC"

T = "ABC"

Minimum window is "BANC".

Note:

If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

This is a typical "substring" problem. People gave many beautiful solutions. 

Solution 1

1. Initialize a vector called remaining, which contains the needed matching numbers of each character in s.
2. If there are still characters needed to be contained (increment i in this case), decrease the matching number of that character and check if it is still non-negative. If it is, then it is the character in t, so decrease the total required number required.
3. If there is no more characters required (increment start in this case), record min andleft if a smaller length is found. Recover the number of this character in the remainingand if it is a character in t increase required.

Solution 2 (Similar to solution 1, but more concise.)
Template that can solve almost all substring problems
The code of solving Longest Substring with At Most Two Distinct Characters is below:
The code of solving Longest Substring Without Repeating Characters is below: