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