# Minimum Window Subsequence

# Problem

You are given two strings, **s1** and **s2**. Your task is to find the smallest **substring** in **s1** such that **s2** appears as a **subsequence** within that substring.

1. The characters of s2 must appear in the same sequence within the substring of s1.
2. If there are multiple valid substrings of the same minimum length, return the one that appears first in s1.
3. If no such substring exists, return an empty string.

**Note:** Both the strings contain only lowercase english letters.

**Examples:**

```plaintext
Input: s1 = "geeksforgeeks", s2 = "eksrg"
Output: "eksforg"
Explanation: "eksforg" satisfies all required conditions. s2 is its subsequence and it is smallest and leftmost among all possible valid substrings of s1.
```

```plaintext
Input: s1 = "abcdebdde", s2 = "bde" 
Output: "bcde"
Explanation:  "bcde" and "bdde" are two substring of s1 where s2 occurs as subsequence but "bcde" occur first so we return that.
```

```plaintext
Input: s1 = "ad", s2 = "b" 
Output: ""
Explanation: There is no substring exists.
```

**Constraints:**

1 ≤ s1.size() ≤ 10<sup>4</sup>\
1 ≤ s2.size() ≤ 50

# Solution

The window must be continuous, and the characters of `s2` must appear **in order** inside it. Other characters may occur between the matches.

## Brute force Approach

Try every starting index `i` in `s1`. Move `j` forward and advance `ptr` only when the characters match.

When `ptr == n`, the full sequence has matched. Record the window if it is shorter, then try the next starting index.

**Time:** O(m²) in the worst case. Matching `n` characters may require scanning much more than `n` positions.

**Extra space:** O(1), excluding the returned string.

```java
class Solution {
    public String minWindow(String s1, String s2) {
        // code here
        int m = s1.length();
        int n = s2.length();
        
        int minLength = Integer.MAX_VALUE;
        int startIndex = m-1;
        
        
        
        for(int i=0; i<m; i++){
            int ptr = 0;
            for(int j=i; j<m; j++){
                
                char chr1 = s1.charAt(j);
                char chr2 = s2.charAt(ptr);
                
                if(chr1 == chr2){
                    ptr+=1;
                }
                
                if(ptr == n){
                    
                    if(minLength > j-i+1){
                        minLength = j-i+1;
                        startIndex = i;
                    }
                    break;
                }
            }
        }
        
        return minLength == Integer.MAX_VALUE ? "" : s1.substring(startIndex, startIndex+minLength);
        
    }
}
```

## Optimal Approach

Use **forward matching + backward shrinking** to avoid retrying from every starting index.

1. **Match forward:** Move `r` until every character of `s2` has matched in order. Save this ending position in `end`.
2. **Match backward:** Set `matched = n - 1` and scan backward. This finds the latest valid start for the fixed `end`.
3. **Record:** The backward loop stops one position before the start, so move `r` forward once before measuring the window.
4. **Repeat:** Reset `matched = 0`. The final `r += 1` starts the next search just after the tightened start, allowing overlapping answers.

### Visual example

```text
s1 = a b x b d e
s2 = b d e

Forward match:   a [b x b d e]
                   b     d e

Backward match:  a b x [b d e]
                       b d e

Tightest window for this end: "bde"
```

The saved `end` stays fixed during shrinking. Reusing `r` for the backward scan finds where the left boundary should move.

**Time:** O(m × n) in the worst case - overlapping searches can revisit characters.

**Extra space:** O(1), excluding the returned string.

```java
class Solution {
    public String minWindow(String s1, String s2) {
        // code here
        int m = s1.length();
        int n = s2.length();
        
        int r = 0;
        
        int startIndex = 0;
        int minLength = Integer.MAX_VALUE;
        
        int matched = 0;
        
        while(r < m){
            
            
            if(s1.charAt(r) == s2.charAt(matched)){
                matched+=1;
            }
            
            if(matched == n){
                matched = n - 1;
                int end = r;
                
                while(matched >= 0){
                    
                    if(s1.charAt(r) == s2.charAt(matched)){
                        matched -= 1;
                    }
                    
                    r-=1;
                }
                
                matched = 0;
                r = r +1;
                
                if(minLength > end - r + 1){
                    minLength = end - r + 1;
                    startIndex = r;
                }
            }
            
            
            r+=1;
        }
        
        return minLength == Integer.MAX_VALUE ? "" :
            s1.substring(startIndex, startIndex + minLength);
     
    }
    
}
```

Both solutions update the answer only for a **strictly shorter** window, so equal-length ties keep the earliest answer. Here, `m = s1.length()` and `n = s2.length()`.