# Minimum Window Subsequence Explained (with Optimized Approach)

## Introduction

The **Minimum Window Subsequence** problem is often confused with **Minimum Window Substring**, but they are **completely different problems**.

In this problem, we are given two strings:

* `s1` → the main string
    
* `s2` → the subsequence string
    

Our task is to find the **smallest contiguous substring of** `s1` such that `s2` appears **as a subsequence** inside it.

## Why Sliding Window (Substring Version) Does NOT Work

In **Minimum Window Substring**, we use:

* frequency maps
    
* shrinking windows based on counts
    

But in **subsequence**:

* order matters
    
* removing a character from the left can break the sequence
    
* window validity is **not monotonic**  
    

so we need to solve with sliding window and greedy approach. We will first get the string which has all s2 characters with forward loop. Then will eleminate unnecessary characters from left by backword loop.

## Algorithm (Step-by-Step)

### Step 1: Forward Scan (Find a Valid Window)

* Start from index `i` in `s1`
    
* Move forward and try to match all characters of `s2` in order
    
* Once matched, we have a valid window `[i … end]`
    

### Step 2: Backward Scan (Minimize the Window)

* Start from `end`
    
* Move backward while matching `s2` in reverse
    
* Stop when all characters are matched
    
* This gives the **smallest valid window ending at** `end`
    

### Step 3: Update Answer

* Compare window length with current minimum
    
* Update result if smaller
    

### Step 4: Move Start Pointer

* Move `i` to `start + 1`
    
* Repeat the process
    

```javascript
/**
 * @param {string} s1
 * @param {string} s2
 * @returns {string}
 */

class Solution {
    minWindow(s1, s2) {
        let n = s1.length
        let m = s2.length
        let min = Infinity
        let ans= ''
        let start = -1
        let i=0
        while(i<n){
            let end = i
            let j=0 //the pointer for s2
            //forward scan
            while(end<n){
                if(s1[end]===s2[j]){
                    j++
                }
               if(j===m){
                   break
               }
               end++
            }
            if (j < m) break;
            //backward to remove unnecessary elements before
            let bp = end
             j = m-1
            while(bp>=i){
                if(j>=0 && s2[j]===s1[bp]){
                    j--
                }
                if (j < 0) break;
                bp--
            }
            
            //check the minimum
            
            if(end-bp+1<min){
                min = end-bp+1
                start=bp
                ans = s1.substring(start, start+min)
            }
            i=bp+1
        }
        return ans
    }
}
```

## **Time Complexity**

The time complexity will be O(m \* n). Space complexity will be O(1)