727. Minimum Window Subsequence

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part.

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

Example 1:

Input: s1 = "abcdebdde", s2 = "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 s2 in the window must occur in order.

Example 2:

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

Constraints:

• 1 <= s1.length <= 2 * 104

• 1 <= s2.length <= 100

• s1 and s2 consist of lowercase English letters.

Solution

With the sliding Window approach, first we iterate the s1, and find a possible subsequence that can meet all the characters of s2 in order,

And then, we start to check if there is a smaller range inside the subsequence by moving the left index from right to 0.

public String minWindow(String s1, String s2) {
    int left = 0, right = 0, len1 = s1.length(), len2 = s2.length();
    int start = -1, end = 0, index = 0;
    while(right < s1.length()) {
        if(s1.charAt(right) == s2.charAt(index)) {
            if(index == len2-1){
                //move left to find the minimized windows
                left = right;
                while(index >= 0){
                    while(s1.charAt(left) != s2.charAt(index)){
                        left--;
                    }
                    left--;
                    index--;
                }
                left++;
                index++;
                if(start == -1 || (end-start) > (right-left+1)){
                    start = left;
                    end = right+1;
                }
                right = left;
            } else{
                index++;
            }
        }
        right++;
    }
    return start == -1 ? "" : s1.substring(start, end);

}