LeetCode 727. Minimum Window Subsequence

Question

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.

Source: https://leetcode.com/problems/minimum-window-subsequence/

Solution

A classic sliding window problem. The main idea is to maintain two pointers for two ends of current window. We first move right forward (expand the window) to find a qualified window, but note that this window may not be the leftmost min window. Then, we move left forward (shrink the window) to minimize current window.

In this problem, when searching a subsequence, we need to care about both character occurrences and character order. A traditional thought is to maintain thest states so that we are able to know whether the window is still qualified after each shrinking step. However, though occurrences can be recorded easily in a map, it is hard to describe the order of characters. This makes it complex to maintain content states of the window. Thus, we do not maintain the content states of subsequences. Instead, when shrinking the window, we do not scan the window from left to right, but right to left. Actually, it would be more appropriate to say that we find a minimized window in a qualified window from left to right.

Note that the next search after a shrink, should start from one step forward to the old left. Because only by doing so, we ensure the completeness of the search.

// s1 original string, s2 pattern
public String minWindow(String s1, String s2) {
    int slen1 = s1.length();
    int slen2 = s2.length();
    // two ends of the window, both inclusive
    int left = 0, right = 0;
    // pattern index to be matched, can be reset multiple times during the search
    int pIndex = 0;
    int minWindowLen = slen1 + 1;
    // start index of left-most min window
    int minWindowStart = 0;

    while (left < slen1 && right < slen1) {
        if (s1.charAt(right) == s2.charAt(pIndex)) {
            if (pIndex == slen2 - 1) {
                // has included the whole pattern,
                // try to shrink the window
                int leftShrink = right;
                int pIndexShrink = slen2 - 1;
                // scan current window from right to left
                while (pIndexShrink >= 0) {
                    if (s1.charAt(leftShrink) == s2.charAt(pIndexShrink)) {
                        pIndexShrink--;
                    }
                    leftShrink--;
                }
                int currentSize = right - leftShrink;
                // only update min window states when current size is smaller
                // in order to get the leftmost min window
                if (currentSize < minWindowLen) {
                    minWindowLen = currentSize;
                    minWindowStart = leftShrink + 1;
                }
                // reset pattern index and start next window search
                pIndex = 0;
                // ensure the completeness of the search.
                left = leftShrink + 2;
                right = left; // TODO: blog
            } else {
                // move forward pattern index
                pIndex++;
                right++;
            }
        } else { // expand the window
            right++;
        }
    }
    return minWindowLen == slen1 + 1 ? "" : s1.substring(minWindowStart, minWindowStart + minWindowLen);
}