Leetcode: Minimum Window Subsequence

 This is the second most commonly asked question on Google. This question heavily involves dynamic programming.

The question is as follows:

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, then return the empty string, and return the one with the left-most starting index if there are multiple strings with this. 

An example is as follows:

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 the elements of T must occur in order.

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

Now onto the solution, which is a dynamic programming one. 

We implement a solution where dp[i][j] stores the index where T is iterated through i and S is iterated through j. 

If T[i - 1] == S[j - 1] we can borrow from the index dp[i - 1][j - 1] to make the current substring valid. Else we only need to borrow from S[j-1] to make the string valid and move from there. 

The final thing to do is to go over the final string to find a substring and attempt to see if a substring length is shorter. 

The first dynamic programming solution, I didn't really understand it, so on to the second one. This time, I will draw a diagram.

We want to know the beginning and end of the character, so we want to find the minimum string that contains T[0:j - 1]. To do this, we perform a diagonal DP if the characters are the same and vertical if they aren't the same, and to find the shortest subsequence, we find the least end number, which will be infinite if this is not possible. The rest of the calculations are intuitive. We compare each character and find the distance between the character sequence matches. 

The time complexity is O(mn). For example, strings "a" and "b" don't have any matches so we denote this as ∞. Same thing for string "bde" until we find the substring in the S string abcdebdde, where the first e is. 

What about "abc" and "b"? We find b successfully with minimum length 2 ("bc") and ending with substring 2 and starting at substring 0 which is from character 1 and including character 2. This denotes "bc" as the proper character. It ends at the index ended and starts at the length of the particular substring. Which is the length of the word that is related ending at the index in S.

class Solution {

    public String minWindow(String S, String T){

        if(S == null || T == null) return "";

        int n = S.length();

        int m = T.length();

        int[][] f = new int[n + 1, m + 1];

        for(int j = 1; j <= m; j++) {

            f[0][j] = Integer.MAX_VALUE/2;

        }

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++) {

                if(S.charAt(i - 1) == T.charAt(j - 1)){

                    f[i][j] = f[i - 1][j - 1] + 1;

                } else {

                    f[i][j] = f[i  - 1][j] + 1;

                }   

            }

        }

        int minLen = Integer.MAX_VALUE;

        int idx = Integer.MAX_VALUE;

        for(int i = 1; i <= n; i++){

            if(f[i][m] < minLen){

                minLen = f[i][m];

                idx = i;      

            }

        }

        return minLen > n ? "" : S.substring(idx - minLen, idx);

    }

}