Code Implementation

class Solution:
    def minWindow(self, S: str, T: str) -> str:
        m, n = len(S), len(T)
        min_len = float('inf')
        start_idx = -1

        i = 0
        while i < m:
            if S[i] == T[0]:
                s_idx = i
                t_idx = 0
                while s_idx < m:
                    if S[s_idx] == T[t_idx]:
                        t_idx += 1
                        if t_idx == n:
                            break
                    s_idx += 1
                if t_idx == n:
                    end = s_idx
                    t_idx = n - 1
                    while s_idx >= i:
                        if S[s_idx] == T[t_idx]:
                            t_idx -= 1
                            if t_idx < 0:
                                break
                        s_idx -= 1
                    s_idx += 1
                    if end - s_idx + 1 < min_len:
                        min_len = end - s_idx + 1
                        start_idx = s_idx
                i = i + 1
            else:
                i += 1
        return "" if start_idx == -1 else S[start_idx:start_idx + min_len]
      

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size();
        int minLen = INT_MAX, startIdx = -1;
        for (int i = 0; i < m; ++i) {
            if (S[i] == T[0]) {
                int s = i, t = 0;
                while (s < m) {
                    if (S[s] == T[t]) {
                        ++t;
                        if (t == n) break;
                    }
                    ++s;
                }
                if (t == n) {
                    int end = s;
                    t = n - 1;
                    while (s >= i) {
                        if (S[s] == T[t]) {
                            --t;
                            if (t < 0) break;
                        }
                        --s;
                    }
                    ++s;
                    if (end - s + 1 < minLen) {
                        minLen = end - s + 1;
                        startIdx = s;
                    }
                }
            }
        }
        return startIdx == -1 ? "" : S.substr(startIdx, minLen);
    }
};
      

class Solution {
    public String minWindow(String S, String T) {
        int m = S.length(), n = T.length();
        int minLen = Integer.MAX_VALUE, startIdx = -1;
        for (int i = 0; i < m; ++i) {
            if (S.charAt(i) == T.charAt(0)) {
                int s = i, t = 0;
                while (s < m) {
                    if (S.charAt(s) == T.charAt(t)) {
                        t++;
                        if (t == n) break;
                    }
                    s++;
                }
                if (t == n) {
                    int end = s;
                    t = n - 1;
                    while (s >= i) {
                        if (S.charAt(s) == T.charAt(t)) {
                            t--;
                            if (t < 0) break;
                        }
                        s--;
                    }
                    s++;
                    if (end - s + 1 < minLen) {
                        minLen = end - s + 1;
                        startIdx = s;
                    }
                }
            }
        }
        return startIdx == -1 ? "" : S.substring(startIdx, startIdx + minLen);
    }
}
      

var minWindow = function(S, T) {
    let m = S.length, n = T.length;
    let minLen = Infinity, startIdx = -1;
    for (let i = 0; i < m; ++i) {
        if (S[i] === T[0]) {
            let s = i, t = 0;
            while (s < m) {
                if (S[s] === T[t]) {
                    t++;
                    if (t === n) break;
                }
                s++;
            }
            if (t === n) {
                let end = s;
                t = n - 1;
                while (s >= i) {
                    if (S[s] === T[t]) {
                        t--;
                        if (t < 0) break;
                    }
                    s--;
                }
                s++;
                if (end - s + 1 < minLen) {
                    minLen = end - s + 1;
                    startIdx = s;
                }
            }
        }
    }
    return startIdx === -1 ? "" : S.substring(startIdx, startIdx + minLen);
};
      

Problem Description

Given two strings, S and T, find the minimum window in S which will contain T as a subsequence. If there is no such window in S that covers all characters in T in order (but not necessarily contiguously), return an empty string. If there are multiple such minimum windows, you can return any one.

• Subsequence means the characters of T appear in S in the same order, but not necessarily together.
• Each character in S can only be used once per window.
• There will always be at most one valid minimum-length window for any input.
• Input strings consist of only ASCII letters, and their lengths are up to a few thousand.

Thought Process

The first idea is to look for all possible substrings of S and check if T is a subsequence of each one. However, this brute-force approach is inefficient, especially for large strings, because there can be a huge number of substrings.

To optimize, we realize that we don't need to check every substring. Instead, we can scan S to find the first occurrence where T can be matched as a subsequence. Once we find such a window, we try to shrink it from the left as much as possible without breaking the subsequence property. By doing this for each possible starting position, we can find the smallest valid window.

The challenge is to efficiently find both the rightmost and leftmost indices for each window, and to avoid redundant work.

Solution Approach

• Step 1: Iterate through each character in S. When you find a character that matches the first character of T, treat this as a potential starting point for a window.
• Step 2: From this starting point, scan forward through S and T simultaneously. For every matching character, advance the pointer in T. If you reach the end of T, you have found a window in S that contains T as a subsequence.
• Step 3: To minimize the window, backtrack from the end of the found window, moving leftward in S and T. For each matching character (from the end of T to the start), move the pointers back. The point where you finish this process is the actual start of the minimal window for this occurrence.
• Step 4: Keep track of the minimum window found so far. Update it whenever you find a smaller valid window.
• Step 5: Continue this process for all starting points in S. At the end, return the smallest window found, or an empty string if no such window exists.

This approach is efficient because it only scans S linearly for each potential start, and backtracks only when a valid window is found.

Example Walkthrough

Let's say S = "abcdebdde" and T = "bde".

1. Start scanning S. First 'b' is at index 1. Try to match T starting from here:
   • At S[1]='b', matches T[0]='b' → advance both.
   • At S[2]='c', no match.
   • At S[3]='d', matches T[1]='d' → advance both.
   • At S[4]='e', matches T[2]='e' → T is fully matched at S[4].
   Now, backtrack to minimize: move left from S[4] and T[2] until all of T is matched in reverse:
   • S[4]='e' matches T[2]='e'
   • S[3]='d' matches T[1]='d'
   • S[1]='b' matches T[0]='b'
   The window is S[1:4] → "bcde".
2. Next, another 'b' at S[5]. Repeat the process:
   • S[5]='b', S[6]='d', S[7]='d', S[8]='e'.
   • Matches found at S[5]='b', S[6]='d', S[8]='e'.
   Backtrack:
   • S[8]='e' matches T[2]
   • S[6]='d' matches T[1]
   • S[5]='b' matches T[0]
   The window is S[5:8] → "bdde", which is shorter than "bcde".
3. No smaller window is found in further iterations.

The answer is "bdde".

Time and Space Complexity

• Brute-force approach: Checking all substrings is O(N² * M), where N is the length of S and M is the length of T. This is not practical for large strings.
• Optimized approach (as above): For each character in S (O(N)), we may scan up to N ahead for a window (in the worst case), and for each window, we backtrack up to M steps. In practice, the total work is O(N*M), since for each potential start, we only scan forward/backward as needed. Space complexity is O(1) (ignoring input/output), as we only track indices and lengths.

Summary

The Minimum Window Subsequence problem requires finding the smallest substring in S that contains T as a subsequence. By scanning for possible windows and shrinking them efficiently, we avoid the brute-force enumeration of all substrings. The key insight is using two pointers to track the matching process and then backtracking to minimize the window. This results in a practical and elegant O(N*M) solution that works efficiently for reasonable input sizes.