0727. Minimum Window Subsequence

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

Description

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.

ac

class Solution {
    public String minWindow(String S, String T) {
        // edge cases
        if (S == null || S.length() == 0 || T == null || T.length() == 0 || S.length() < T.length())
            return "";

        int slen = S.length(), tlen = T.length();
        int[][] dp = new int[tlen+1][slen+1];  // dp[i][j] means start index of substring in 
        // init 1st row
        for (int c = 0; c < dp[0].length; c++) {
            dp[0][c] = c+1;
        }

        for (int r = 1; r < dp.length; r++) {
            for (int c = 1; c < dp[0].length; c++) {
                if (T.charAt(r-1) == S.charAt(c-1)) {
                    dp[r][c] = dp[r-1][c-1];
                } else {
                    dp[r][c] = dp[r][c-1];
                }
            }
        }

        // iterate last row, get result
        int min = Integer.MAX_VALUE, start = 0;
        for (int c = 1; c < dp[0].length; c++) {
            int len = c - dp[tlen][c] + 1;
            if (dp[tlen][c] != 0 && len < min) { // find shorter length, update
                start = dp[tlen][c]-1;
                min = len;
            }
        }

        // result
        return min == Integer.MAX_VALUE ? "" : S.substring(start, start+min);
    }
}

this version is more intuitive:

class Solution {
    public String minWindow(String S, String T) {
        // edge cases
        if (S == null || S.length() == 0 || T == null || T.length() == 0 || S.length() < T.length())
            return "";

        int slen = S.length(), tlen = T.length();
        int[][] dp = new int[tlen][slen];  // dp[i][j] means start index of substring in 
        // init 1st row
        // for (int c = 0; c < slen; c++) {
        //     if (T.charAt(0) == S.charAt(c)) dp[0][c] = c;
        // }

        for (int r = 0; r < tlen; r++) {
            for (int c = 0; c < slen; c++) {
                if (T.charAt(r) == S.charAt(c)) {
                    dp[r][c] = r == 0 ? c : c == 0 ? -1 : dp[r-1][c-1];
                } else {
                    dp[r][c] = c == 0 ? -1 : dp[r][c-1];
                }
            }
        }

        // iterate last row, get result
        int min = Integer.MAX_VALUE, start = 0;
        for (int c = 0; c < slen; c++) {
            int len = c - dp[tlen-1][c] + 1;
            if (dp[tlen-1][c] != -1 && len < min) { // find shorter length, update
                start = dp[tlen-1][c];
                min = len;
            }
        }

        // result
        return min == Integer.MAX_VALUE ? "" : S.substring(start, start+min);
    }
}