LeetCode 727: Minimum Window Subsequence Solution

Master LeetCode problem 727 (Minimum Window Subsequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

727. Minimum Window Subsequence

Hard

String Dynamic Programming Sliding Window

Problem Explanation

Explanation:

This problem can be solved using dynamic programming. We can iterate through the string S and maintain a 2D array dp, where dp[i][j] represents the index of the first occurrence of character T[j] in the substring S[0:i]. We can update this array by comparing the current character of S with the character at T[j]. We also maintain a variable start to keep track of the start index of the minimum window found so far.

At each step, we update the dp array and check if we have found a valid window containing the subsequence T. If a valid window is found, we update the start index and the minimum window length.

Finally, we return the substring of S starting from the start index with minimum window length.

: :

Solution Code

class Solution {
    public String minWindow(String S, String T) {
        int m = S.length(), n = T.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i + 1;
        }
        
        int minLen = Integer.MAX_VALUE;
        int start = -1;
        
        for (int i = 1; i <= m; i++) {
            int k = 0;
            for (int j = 1; j <= n; j++) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][k];
                    if (++k == n) {
                        k--;
                        int end = i;
                        while (--k >= 0) {
                            while (S.charAt(--i) != T.charAt(k));
                        }
                        if (end - i < minLen) {
                            minLen = end - (start = i);
                        }
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return start == -1 ? "" : S.substring(start, start + minLen);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 727 (Minimum Window Subsequence)?

This page provides optimized solutions for LeetCode problem 727 (Minimum Window Subsequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 727 (Minimum Window Subsequence)?

The time complexity for LeetCode 727 (Minimum Window Subsequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 727 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 727 in Java, C++, or Python.

Back to LeetCode Solutions