Minimum Window Subsequence [Hard] — Forward + Backward Two Ptr

Problem Statement

Find the minimum window in string s such that t is a subsequence of that window. Return "" if none.

Input: s="abcdebdde", t="bde" → Output: "bcde"

Intuition

Forward scan: match all of t in s, find right boundary. Backward scan from right boundary: rematch t reversed to find tight left. This gives shortest window ending at that right.

Solutions

Python

def minWindow(s: str, t: str) -> str:
    ans = ""
    i = 0
    while i < len(s):
        # Forward: find window end
        j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]: j += 1
            i += 1
        if j < len(t): break
        # Backward: minimize window
        k = i - 1; j = len(t) - 1
        while j >= 0:
            if s[k] == t[j]: j -= 1
            k -= 1
        k += 1
        if not ans or i - k < len(ans):
            ans = s[k:i]
        i = k + 1
    return ans

C++

string minWindow(string s, string t) {
    string ans=""; int i=0,n=s.size(),m=t.size();
    while(i<n){
        int j=0;
        while(i<n&&j<m){if(s[i]==t[j])j++;i++;}
        if(j<m) break;
        int k=i-1; j=m-1;
        while(j>=0){if(s[k]==t[j])j--;k--;}k++;
        if(ans.empty()||i-k<(int)ans.size()) ans=s.substr(k,i-k);
        i=k+1;
    }
    return ans;
}

Complexity

Time: O(|s|×|t|) worst, O(|s|) typical
Space: O(1)