Minimum Window Subsequence Using Two Pointers

Given two strings S and T, find the minimum window in S which will contain all the characters in T in the same order (as a subsequence).

If there is no such window in S that covers all characters in T, return an empty string. If multiple such windows exist, return the one with the smallest starting index.

Input: S = "abcdebdde", T = "bde"
Output: "bcde"

Understanding the Problem

We are given two strings S and T. Our goal is to find the smallest window in S such that all characters of T appear in order as a subsequence.

A subsequence means the characters of T must appear in S in the same order, but not necessarily consecutively.

If there are multiple valid windows, we return the one that starts first. If there is no such window, we return an empty string.

Step-by-Step Solution with Example

Step 1: Understand the Example

S = "abcdebdde", T = "bde"

We need the shortest substring of S that contains 'b', then 'd', then 'e' in order.

Answer: "bcde" is the smallest valid window.

Step 2: Two Pointers Technique

We use two pointers:

• A forward pointer i that scans through S
• A second pointer j that walks through T to match the subsequence

Step 3: Forward Scan

We move i from left to right through S. Each time S[i] matches T[0], we try to match the full T subsequence from that point onward.

Step 4: Match the Entire T

Once T is fully matched by advancing both i and j, we record the end position (where the match finishes in S).

Step 5: Backward Shrink to Minimize Window

We now try to shrink the window by moving backward from end using a new pointer. We go backwards matching characters of T in reverse order to find the start of this minimum window.

Step 6: Update Minimum Window

If the window found is smaller than the previously recorded one, we update our result (minimum length and starting index).

Step 7: Continue Search

We move forward in S and repeat the process until we reach the end of S.

Step 8: Return Result

If a valid window was found, return the substring. Otherwise, return "".

Edge Cases

• T is longer than S → Impossible to form a window → Return ""
• T is empty → By definition, every string contains an empty subsequence → Return "" or handle based on constraints
• Multiple windows found → Return the one with the smallest start index
• No match found → Return empty string

Final Thoughts

This problem is a great example of combining the sliding window and two-pointer technique to solve subsequence matching problems efficiently. The key idea is to move forward to find a valid window, and then move backward to minimize it. This technique avoids checking all substrings and saves time.

With a clear understanding of how to scan forward and shrink backward, we can handle both normal and edge cases smoothly.

1. Initialize variables: start = 0 and minLen = infinity to track the minimum window.
2. Use a forward pointer i to traverse string S.
3. When S[i] matches the first character of T, attempt to find a full match of T in S starting from i.
4. → Use a second pointer j to walk through T while i moves forward to match each character.
5. → If all characters of T are matched, track the ending index end and begin shrinking the window backwards from end to find the leftmost start that still keeps T in order.
6. → Use reverse pointers to backtrack and identify the minimum window start and update minLen and start if the current window is smaller.
7. Continue until the end of S is reached.
8. Return S.substr(start, minLen) if minLen != infinity, otherwise return "".

def min_window_subsequence(S: str, T: str) -> str:
    n, m = len(S), len(T)
    min_len = float('inf')
    start = 0

    i = 0
    while i < n:
        if S[i] == T[0]:
            t_idx = 0
            j = i
            # Forward match to find subsequence
            while j < n and t_idx < m:
                if S[j] == T[t_idx]:
                    t_idx += 1
                j += 1
            if t_idx == m:  # Full match found
                end = j - 1
                # Backward shrink to find minimal start
                t_idx = m - 1
                k = end
                while k >= i:
                    if S[k] == T[t_idx]:
                        t_idx -= 1
                        if t_idx < 0:
                            break
                    k -= 1
                window_len = end - k + 1
                if window_len < min_len:
                    min_len = window_len
                    start = k
                i = k  # Move i to start of found window
        i += 1

    return S[start:start+min_len] if min_len != float('inf') else ""

# Example usage
S = "abcdebdde"
T = "bde"
print(min_window_subsequence(S, T))  # Output: "bcde"

public class MinWindowSubsequence {
    public static String minWindow(String S, String T) {
        int n = S.length(), m = T.length();
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        for (int i = 0; i < n; i++) {
            if (S.charAt(i) == T.charAt(0)) {
                int tIdx = 0;
                int j = i;
                // Forward match
                while (j < n && tIdx < m) {
                    if (S.charAt(j) == T.charAt(tIdx)) {
                        tIdx++;
                    }
                    j++;
                }

                if (tIdx == m) { // matched all
                    int end = j - 1;
                    tIdx = m - 1;
                    int k = end;
                    // Backward shrink
                    while (k >= i) {
                        if (S.charAt(k) == T.charAt(tIdx)) {
                            tIdx--;
                            if (tIdx < 0) break;
                        }
                        k--;
                    }
                    int windowLen = end - k + 1;
                    if (windowLen < minLen) {
                        minLen = windowLen;
                        start = k;
                    }
                    i = k; // jump to k
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : S.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        String S = "abcdebdde";
        String T = "bde";
        System.out.println(minWindow(S, T)); // Output: bcde
    }
}

function minWindowSubsequence(S, T) {
  const n = S.length, m = T.length;
  let minLen = Infinity, start = 0;

  for (let i = 0; i < n; i++) {
    if (S[i] === T[0]) {
      let tIdx = 0, j = i;
      // Forward match
      while (j < n && tIdx < m) {
        if (S[j] === T[tIdx]) tIdx++;
        j++;
      }
      if (tIdx === m) {
        let end = j - 1;
        tIdx = m - 1;
        let k = end;
        // Backward shrink
        while (k >= i) {
          if (S[k] === T[tIdx]) {
            tIdx--;
            if (tIdx < 0) break;
          }
          k--;
        }
        let windowLen = end - k + 1;
        if (windowLen < minLen) {
          minLen = windowLen;
          start = k;
        }
        i = k; // jump to start of window
      }
    }
  }

  return minLen === Infinity ? "" : S.substring(start, start + minLen);
}

// Example
const S = "abcdebdde";
const T = "bde";
console.log(minWindowSubsequence(S, T)); // Output: bcde

#include <stdio.h>
#include <string.h>
#include <limits.h>

char* minWindowSubsequence(char* S, char* T) {
    int n = strlen(S), m = strlen(T);
    int minLen = INT_MAX, start = 0;

    for (int i = 0; i < n; i++) {
        if (S[i] == T[0]) {
            int tIdx = 0, j = i;
            // Forward match
            while (j < n && tIdx < m) {
                if (S[j] == T[tIdx]) tIdx++;
                j++;
            }
            if (tIdx == m) {
                int end = j - 1;
                tIdx = m - 1;
                int k = end;
                // Backward shrink
                while (k >= i) {
                    if (S[k] == T[tIdx]) {
                        tIdx--;
                        if (tIdx < 0) break;
                    }
                    k--;
                }
                int windowLen = end - k + 1;
                if (windowLen < minLen) {
                    minLen = windowLen;
                    start = k;
                }
                i = k;
            }
        }
    }

    if (minLen == INT_MAX) {
        return "";
    }

    static char result[1000];
    strncpy(result, S + start, minLen);
    result[minLen] = '\0';
    return result;
}

int main() {
    char S[] = "abcdebdde";
    char T[] = "bde";
    char* res = minWindowSubsequence(S, T);
    printf("%s\n", res); // Output: bcde
    return 0;
}

#include <iostream>
#include <string>
#include <climits>
using namespace std;

string minWindowSubsequence(const string& S, const string& T) {
    int n = S.size(), m = T.size();
    int minLen = INT_MAX, start = 0;

    for (int i = 0; i < n; i++) {
        if (S[i] == T[0]) {
            int tIdx = 0, j = i;
            while (j < n && tIdx < m) {
                if (S[j] == T[tIdx]) tIdx++;
                j++;
            }
            if (tIdx == m) {
                int end = j - 1;
                tIdx = m - 1;
                int k = end;
                while (k >= i) {
                    if (S[k] == T[tIdx]) {
                        tIdx--;
                        if (tIdx < 0) break;
                    }
                    k--;
                }
                int windowLen = end - k + 1;
                if (windowLen < minLen) {
                    minLen = windowLen;
                    start = k;
                }
                i = k;
            }
        }
    }

    if (minLen == INT_MAX) return "";
    return S.substr(start, minLen);
}

int main() {
    string S = "abcdebdde";
    string T = "bde";
    cout << minWindowSubsequence(S, T) << endl; // Output: bcde
    return 0;
}

package main

import (
	"fmt"
)

func minWindowSubsequence(S, T string) string {
	n, m := len(S), len(T)
	minLen := 1<<31 - 1
	start := 0

	for i := 0; i < n; i++ {
		if S[i] == T[0] {
			tIdx := 0
			j := i
			for j < n && tIdx < m {
				if S[j] == T[tIdx] {
					tIdx++
				}
				j++
			}
			if tIdx == m {
				end := j - 1
				tIdx = m - 1
				k := end
				for k >= i {
					if S[k] == T[tIdx] {
						tIdx--
						if tIdx < 0 {
							break
						}
					}
					k--
				}
				windowLen := end - k + 1
				if windowLen < minLen {
					minLen = windowLen
					start = k
				}
				i = k
			}
		}
	}

	if minLen == 1<<31 - 1 {
		return ""
	}
	return S[start : start+minLen]
}

func main() {
	S := "abcdebdde"
	T := "bde"
	fmt.Println(minWindowSubsequence(S, T)) // Output: bcde
}

fn min_window_subsequence(S: &str, T: &str) -> String {
    let n = S.len();
    let m = T.len();
    let s_chars: Vec<char> = S.chars().collect();
    let t_chars: Vec<char> = T.chars().collect();
    let mut min_len = usize::MAX;
    let mut start = 0;

    let mut i = 0;
    while i < n {
        if s_chars[i] == t_chars[0] {
            let mut t_idx = 0;
            let mut j = i;
            while j < n && t_idx < m {
                if s_chars[j] == t_chars[t_idx] {
                    t_idx += 1;
                }
                j += 1;
            }
            if t_idx == m {
                let end = j - 1;
                let mut t_idx = m as isize - 1;
                let mut k = end as isize;
                while k >= i as isize {
                    if s_chars[k as usize] == t_chars[t_idx as usize] {
                        t_idx -= 1;
                        if t_idx < 0 {
                            break;
                        }
                    }
                    k -= 1;
                }
                let window_len = end - k as usize + 1;
                if window_len < min_len {
                    min_len = window_len;
                    start = k as usize;
                }
                i = k as usize;
            }
        }
        i += 1;
    }

    if min_len == usize::MAX {
        return String::new();
    }

    S.chars().skip(start).take(min_len).collect()
}

fn main() {
    let S = "abcdebdde";
    let T = "bde";
    println!("{}", min_window_subsequence(S, T)); // Output: bcde
}

fun minWindowSubsequence(S: String, T: String): String {
    val n = S.length
    val m = T.length
    var minLen = Int.MAX_VALUE
    var start = 0
    var i = 0

    while (i < n) {
        if (S[i] == T[0]) {
            var tIdx = 0
            var j = i
            while (j < n && tIdx < m) {
                if (S[j] == T[tIdx]) tIdx++
                j++
            }
            if (tIdx == m) {
                val end = j - 1
                var tIdxBack = m - 1
                var k = end
                while (k >= i) {
                    if (S[k] == T[tIdxBack]) {
                        tIdxBack--
                        if (tIdxBack < 0) break
                    }
                    k--
                }
                val windowLen = end - k + 1
                if (windowLen < minLen) {
                    minLen = windowLen
                    start = k
                }
                i = k
            }
        }
        i++
    }

    return if (minLen == Int.MAX_VALUE) "" else S.substring(start, start + minLen)
}

fun main() {
    val S = "abcdebdde"
    val T = "bde"
    println(minWindowSubsequence(S, T)) // Output: bcde
}

func minWindowSubsequence(_ S: String, _ T: String) -> String {
    let n = S.count
    let m = T.count
    let sChars = Array(S)
    let tChars = Array(T)
    var minLen = Int.max
    var start = 0
    var i = 0

    while i < n {
        if sChars[i] == tChars[0] {
            var tIdx = 0
            var j = i
            while j < n && tIdx < m {
                if sChars[j] == tChars[tIdx] {
                    tIdx += 1
                }
                j += 1
            }
            if tIdx == m {
                let end = j - 1
                var tIdxBack = m - 1
                var k = end
                while k >= i {
                    if sChars[k] == tChars[tIdxBack] {
                        tIdxBack -= 1
                        if tIdxBack < 0 { break }
                    }
                    k -= 1
                }
                let windowLen = end - k + 1
                if windowLen < minLen {
                    minLen = windowLen
                    start = k
                }
                i = k
            }
        }
        i += 1
    }

    if minLen == Int.max {
        return ""
    }
    return String(sChars[start..<start + minLen])
}

// Example
let S = "abcdebdde"
let T = "bde"
print(minWindowSubsequence(S, T)) // Output: bcde

function minWindowSubsequence(S: string, T: string): string {
  const n = S.length, m = T.length;
  let minLen = Infinity, start = 0;

  for (let i = 0; i < n; i++) {
    if (S[i] === T[0]) {
      let tIdx = 0, j = i;
      while (j < n && tIdx < m) {
        if (S[j] === T[tIdx]) tIdx++;
        j++;
      }
      if (tIdx === m) {
        const end = j - 1;
        tIdx = m - 1;
        let k = end;
        while (k >= i) {
          if (S[k] === T[tIdx]) {
            tIdx--;
            if (tIdx < 0) break;
          }
          k--;
        }
        const windowLen = end - k + 1;
        if (windowLen < minLen) {
          minLen = windowLen;
          start = k;
        }
        i = k;
      }
    }
  }

  return minLen === Infinity ? "" : S.substring(start, start + minLen);
}

// Example usage
const S = "abcdebdde";
const T = "bde";
console.log(minWindowSubsequence(S, T)); // Output: bcde

Time complexity

Space complexity

O(1)

Only a few pointers and constant variables are used for tracking the window and indices. No additional space is required proportional to the size of input strings.