Minimum Window Subsequence

Problem Statement

Given two strings:

s1 → main string
s2 → pattern string

Find the smallest substring of s1 such that s2 appears as a subsequence inside it.

Rules:

Characters of s2 must appear in order (not necessarily contiguous)
Return the smallest valid window
If multiple answers exist, return the leftmost one
If none exists, return ""

Example

Input

s1 = "geeksforgeeks"
s2 = "eksrg"

Output

eksforg

Key Insight

This is NOT a sliding window problem.

Instead, we use a Two Phase Greedy Scan:

Phase 1: Forward Scan

Find where s2 fully matches as a subsequence inside s1.

Phase 2: Backward Scan

Once matched, move backward to shrink the window to minimum size.

Why Backtracking is Needed

Forward matching gives a valid window, but:

It may not be the smallest.

So we go backward to find the tightest starting point.

Step-by-Step Dry Run

Input

s1 = geeksforgeeks
s2 = eksrg

Forward Matching

We try to match "eksrg":

geeksforgeeks
   ^^^^
   eksr matched

We reach:

end = position of 'g'

Backward Shrinking

We move backward to find earliest start:

geeksforgeeks
 ↑
start found at 'e'

So final window becomes:

eksforg

All Valid Windows

For this input:

eksforg   (smallest + leftmost)
ksforg    (not leftmost)

Java Solution

class Solution {
    public String minWindow(String s1, String s2) {
        int n = s1.length(), m = s2.length();

        int minLen = Integer.MAX_VALUE;
        String ans = "";

        int i = 0;

        while (i < n) {
            int j = 0;

            // Forward scan (match subsequence)
            while (i < n) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    j++;
                    if (j == m) break;
                }
                i++;
            }

            // Not fully matched
            if (j < m) break;

            int end = i;

            // Backward shrink
            j = m - 1;
            while (i >= 0) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    j--;
                    if (j < 0) break;
                }
                i--;
            }

            int start = i + 1;

            String window = s1.substring(start, end + 1);

            if (window.length() < minLen) {
                minLen = window.length();
                ans = window;
            }

            // move forward for next attempt
            i = start + 1;
        }

        return ans;
    }
}

Complexity

Time: O(n × m)
Space: O(1)

Key Takeaways

Subsequence problems often use two-pass scanning
Forward scan ensures validity
Backward scan ensures minimal window
Greedy + backtracking is the core idea

Pattern Recognition

This problem is related to:

Subsequence matching
Greedy string algorithms
Two pointer + backtracking
DP string optimization (alternative approach)

Final Output

Input

geeksforgeeks
eksrg

Output

eksforg