LeetCode 727. Minimum Window Subsequence

原题链接在这里：https://leetcode.com/problems/minimum-window-subsequence/

题目：

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Note:

• All the strings in the input will only contain lowercase letters.
• The length of S will be in the range [1, 20000].
• The length of T will be in the range [1, 100].

题解：

Having a pointer j pointing at T index, when S[i] == T[j], move j++.

When j hits T.length(), then we find a substring candidate. Set a end to mark current position at S.

We need to move i and j back, when j hits 0, now if S.substring(i+ 1, end) length is smaller than minLen, update minWin.

Time Complexity: O(m*n). m = S.length(), n = T.length(). S = "aaaaaa", T = "aas", for each char in S, it is visited 2 * T.length() times.

Space: O(1). 

AC Java:

class Solution {
    public String minWindow(String S, String T) {
        String minWin = "";
        int j = 0;
        int minLen = S.length() + 1;
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == T.charAt(j)){
                j++;
            }
            
            if(j == T.length()){
                int end = i + 1;
                j--;
                while(j >= 0){
                    if(T.charAt(j) == S.charAt(i)){
                        j--;
                    }
                    
                    i--;
                }
                
                if(end - i + 1 < minLen){
                    minLen = end - i + 1;
                    minWin = S.substring(i + 1, end);
                }
                
                j++;
                i++;
            }
        }
        
        return minWin;
    }
}

类似Number of Longest Increasing Subsequence, Minimum Window Substring.