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:

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.

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.

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

Constraints:

1 ≤ s1.size() ≤ 10⁴
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.

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

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.

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().