Minimum Window Subsequence

Intuition

Find smallest window in S that contains T as a subsequence. DP: dp[i][j] = start index of smallest window in S[0..i] containing T[0..j].

Algorithm

1Two-pointer: for each occurrence of T[0] in S, extend to find full T match, then shrink from start.
2Forward: find first index where S[i..] contains T. Backward: from that end, find last occurrence of T match.

Common Pitfalls

•Not substring but subsequence. Forward-backward two-pass approach is O(n*m).

Minimum Window Subsequence.java

Java

// Approach: Two-pointer: expand right to find subsequence, then contract left to minimize window.
// Time: O(n * m) Space: O(1)
class Solution {
    public String minWindow(String s1, String s2) {
        int i = 0, j = 0, k = 0;
        int res = Integer.MAX_VALUE;

        String str = "";

        while (j < s1.length() && k < s2.length()) {
            if (s1.charAt(j) == s2.charAt(k))
                k++;

            if (k == s2.length()) {
                i = j;

                k = s2.length() - 1;

                while (i >= 0 && k >= 0) {
                    if (s1.charAt(i) == s2.charAt(k))
                        k--;
                    i--;
                }

                i++;

                if (res > j - i + 1) {
                    res = j - i + 1;
                    str = s1.substring(i, j + 1);
                }
                k = 0;
                j = i + 1;

            }
            j++;
        }
        
        return str;
    }
}

Was this solution helpful?