Given two strings s1 and s2, find the smallest contiguous substring of s1 in which s2 appears as a subsequence.
- The characters of s2 must appear in the same order within the substring, but not necessarily consecutively.
- If multiple substrings of the same minimum length satisfy the condition, return the one that appears earliest in s1.
- If no such substring exists, return an empty string.
- Both s1 and s2 consist only of 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.
Try it on GfG Practice
Table of Content
[Naive Approach] Brute Force with Substring and Subsequence Check - O(n^3) Time and O(1) Space
The idea is to iterate through all possible substrings of s1 and check each one to see if s2 appears as a subsequence within it. We keep track of the shortest substring that meets this condition, updating whenever we find a smaller one.
If multiple substrings have the same length, the first occurring one is selected. If no substring contains s2 as a subsequence, we return an empty string.
#include <iostream>
#include <string>
#include <climits>
using namespace std;
// function to check if s2 is a subsequence of sub
bool isSubsequence(string &sub, string &s2) {
int i = 0, j = 0;
while (i < sub.size() && j < s2.size()) {
if (sub[i] == s2[j]) j++;
i++;
}
return j == s2.size();
}
// function to find the smallest substring of s1
// containing s2 as subsequence
string minWindow(string &s1, string &s2) {
int n = s1.size();
string ans = "";
int minLen = INT_MAX;
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
string sub = s1.substr(start, end - start + 1);
if (isSubsequence(sub, s2)) {
if (sub.size() < minLen) {
minLen = sub.size();
ans = sub;
}
// no need to extend further for this start
// as we want smallest
break;
}
}
}
return ans;
}
int main() {
string s1 = "abcdebdde";
string s2 = "bde";
cout << minWindow(s1, s2) << endl;
return 0;
}
class GfG {
// function to check if s2 is a subsequence of sub
static boolean isSubsequence(String sub, String s2) {
int i = 0, j = 0;
while (i < sub.length() && j < s2.length()) {
if (sub.charAt(i) == s2.charAt(j)) j++;
i++;
}
return j == s2.length();
}
// function to find the smallest substring of s1
// containing s2 as subsequence
static String minWindow(String s1, String s2) {
int n = s1.length();
String ans = "";
int minLen = Integer.MAX_VALUE;
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
String sub = s1.substring(start, end + 1);
if (isSubsequence(sub, s2)) {
if (sub.length() < minLen) {
minLen = sub.length();
ans = sub;
}
// no need to extend further for this start
// as we want smallest
break;
}
}
}
return ans;
}
public static void main(String[] args) {
String s1 = "abcdebdde";
String s2 = "bde";
System.out.println(minWindow(s1, s2));
}
}
# function to check if s2 is a subsequence of sub
def isSubsequence(sub, s2):
i = 0
j = 0
while i < len(sub) and j < len(s2):
if sub[i] == s2[j]:
j += 1
i += 1
return j == len(s2)
# function to find the smallest substring of s1
# containing s2 as subsequence
def minWindow(s1, s2):
n = len(s1)
ans = ""
minLen = float('inf')
for start in range(n):
for end in range(start, n):
sub = s1[start:end + 1]
if isSubsequence(sub, s2):
if len(sub) < minLen:
minLen = len(sub)
ans = sub
# no need to extend further for this start
# as we want smallest
break
return ans
if __name__ == "__main__":
s1 = "abcdebdde"
s2 = "bde"
print(minWindow(s1, s2))
using System;
class GfG {
// function to check if s2 is a subsequence of sub
static bool isSubsequence(string sub, string s2) {
int i = 0, j = 0;
while (i < sub.Length && j < s2.Length) {
if (sub[i] == s2[j]) j++;
i++;
}
return j == s2.Length;
}
// function to find the smallest substring of s1
// containing s2 as subsequence
static string minWindow(string s1, string s2) {
int n = s1.Length;
string ans = "";
int minLen = int.MaxValue;
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
string sub = s1.Substring(start, end - start + 1);
if (isSubsequence(sub, s2)) {
if (sub.Length < minLen) {
minLen = sub.Length;
ans = sub;
}
// no need to extend further for this start
// as we want smallest
break;
}
}
}
return ans;
}
public static void Main(string[] args) {
string s1 = "abcdebdde";
string s2 = "bde";
Console.WriteLine(minWindow(s1, s2));
}
}
// function to check if s2 is a subsequence of sub
function isSubsequence(sub, s2) {
let i = 0, j = 0;
while (i < sub.length && j < s2.length) {
if (sub[i] === s2[j]) j++;
i++;
}
return j === s2.length;
}
// function to find the smallest substring of s1
// containing s2 as subsequence
function minWindow(s1, s2) {
let n = s1.length;
let ans = "";
let minLen = Number.MAX_SAFE_INTEGER;
for (let start = 0; start < n; start++) {
for (let end = start; end < n; end++) {
let sub = s1.substring(start, end + 1);
if (isSubsequence(sub, s2)) {
if (sub.length < minLen) {
minLen = sub.length;
ans = sub;
}
// no need to extend further for this start
// as we want smallest
break;
}
}
}
return ans;
}
// Driver Code
let s1 = "abcdebdde";
let s2 = "bde";
console.log(minWindow(s1, s2));
Output
bcde
[Better Approach] Two-Pointer Forward Scan with Backtracking - O(n^2) Time and O(1) Space
The idea is to iterate through s1 and, for each position where the first character of s2 matches, move forward with two pointers to find the complete subsequence s2.
Once matched, backtrack from the end position to shrink the window to the smallest substring that still contains s2 as a subsequence.
Track the minimum-length substring found and update it whenever a smaller one is discovered.
If no match is found, return an empty string.
#include <iostream>
#include <climits>
#include <string>
using namespace std;
string minWindow(string &s1, string &s2) {
int n = s1.size();
int m = s2.size();
string ans = "";
int minLen = INT_MAX;
for (int i = 0; i < n; i++) {
// find starting point where s1[i] matches s2[0]
if (s1[i] == s2[0]) {
int p1 = i, p2 = 0;
// move forward until s2 is matched
while (p1 < n && p2 < m) {
if (s1[p1] == s2[p2]) p2++;
p1++;
}
// if we matched all characters of s2
if (p2 == m) {
// last matched index
int end = p1 - 1;
p2 = m - 1;
// backtrack to find minimal starting index
while (end >= i) {
if (s1[end] == s2[p2]) p2--;
if (p2 < 0) break;
end--;
}
int start = end;
int len = p1 - start;
if (len < minLen) {
minLen = len;
ans = s1.substr(start, len);
}
}
}
}
return ans;
}
int main() {
string s1 = "abcdebdde";
string s2 = "bde";
cout << minWindow(s1, s2) << endl;
return 0;
}
class GfG {
static String minWindow(String s1, String s2) {
int n = s1.length();
int m = s2.length();
String ans = "";
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// find starting point where s1[i] matches s2[0]
if (s1.charAt(i) == s2.charAt(0)) {
int p1 = i, p2 = 0;
// move forward until s2 is matched
while (p1 < n && p2 < m) {
if (s1.charAt(p1) == s2.charAt(p2)) p2++;
p1++;
}
// if we matched all characters of s2
if (p2 == m) {
// last matched index
int end = p1 - 1;
p2 = m - 1;
// backtrack to find minimal starting index
while (end >= i) {
if (s1.charAt(end) == s2.charAt(p2)) p2--;
if (p2 < 0) break;
end--;
}
int start = end;
int len = p1 - start;
if (len < minLen) {
minLen = len;
ans = s1.substring(start, start + len);
}
}
}
}
return ans;
}
public static void main(String[] args) {
String s1 = "abcdebdde";
String s2 = "bde";
System.out.println(minWindow(s1, s2));
}
}
def minWindow(s1, s2):
n = len(s1)
m = len(s2)
ans = ""
minLen = float('inf')
for i in range(n):
# find starting point where s1[i] matches s2[0]
if s1[i] == s2[0]:
p1, p2 = i, 0
# move forward until s2 is matched
while p1 < n and p2 < m:
if s1[p1] == s2[p2]:
p2 += 1
p1 += 1
# if we matched all characters of s2
if p2 == m:
# last matched index
end = p1 - 1
p2 = m - 1
# backtrack to find minimal starting index
while end >= i:
if s1[end] == s2[p2]:
p2 -= 1
if p2 < 0:
break
end -= 1
start = end
length = p1 - start
if length < minLen:
minLen = length
ans = s1[start:start + length]
return ans
if __name__ == "__main__":
s1 = "abcdebdde"
s2 = "bde"
print(minWindow(s1, s2))
using System;
class GfG {
static string minWindow(string s1, string s2) {
int n = s1.Length;
int m = s2.Length;
string ans = "";
int minLen = int.MaxValue;
for (int i = 0; i < n; i++) {
// find starting point where s1[i] matches s2[0]
if (s1[i] == s2[0]) {
int p1 = i, p2 = 0;
// move forward until s2 is matched
while (p1 < n && p2 < m) {
if (s1[p1] == s2[p2]) p2++;
p1++;
}
// if we matched all characters of s2
if (p2 == m) {
// last matched index
int end = p1 - 1;
p2 = m - 1;
// backtrack to find minimal starting index
while (end >= i) {
if (s1[end] == s2[p2]) p2--;
if (p2 < 0) break;
end--;
}
int start = end;
int len = p1 - start;
if (len < minLen) {
minLen = len;
ans = s1.Substring(start, len);
}
}
}
}
return ans;
}
public static void Main(string[] args) {
string s1 = "abcdebdde";
string s2 = "bde";
Console.WriteLine(minWindow(s1, s2));
}
}
function minWindow(s1, s2) {
let n = s1.length;
let m = s2.length;
let ans = "";
let minLen = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
// find starting point where s1[i] matches s2[0]
if (s1[i] === s2[0]) {
let p1 = i, p2 = 0;
// move forward until s2 is matched
while (p1 < n && p2 < m) {
if (s1[p1] === s2[p2]) p2++;
p1++;
}
// if we matched all characters of s2
if (p2 === m) {
// last matched index
let end = p1 - 1;
p2 = m - 1;
// backtrack to find minimal starting index
while (end >= i) {
if (s1[end] === s2[p2]) p2--;
if (p2 < 0) break;
end--;
}
let start = end;
let len = p1 - start;
if (len < minLen) {
minLen = len;
ans = s1.substring(start, start + len);
}
}
}
}
return ans;
}
// Driver Code
let s1 = "abcdebdde";
let s2 = "bde";
console.log(minWindow(s1, s2));
Output
bcde
[Expected Approach] Preprocessing with Next Occurrence Table - O(n × m) Time and O(n) Time
The idea is to preprocess s1 so we can quickly jump to the next occurrence of any character, instead of scanning it repeatedly.
We create a nextPos table where nextPos[i][ch] stores the index of the next occurrence of character ch after position i in s1. This table is filled by traversing s1 from right to left.
Then, for each possible starting position in s1 that matches the first character of s2, we try to match all characters of s2 by repeatedly jumping through the nextPos table.
If we successfully match all of s2, we track the minimal window length and update the answer.
Step by Step Approach:
- Build nextPos table where nextPos[i][c] stores the next occurrence of character c in s1 at or after index i.
- Fill nextPos from right to left so each position knows where each letter appears next.
- For each index in s1 matching the first character of s2, try to match s2 by jumping using nextPos.
- If a complete match is found, record the window and update the smallest one found so far.
- Return the smallest window substring containing s2 as a subsequence.
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;
string minWindow(string &s1, string &s2) {
int n = s1.size();
int m = s2.size();
// nextPos[i][ch] : next occurrence of character
// ch after index i in s1
vector<vector<int>> nextPos(n + 2, vector<int>(26, -1));
// initialize last row with -1 (no occurrence beyond end)
for (int c = 0; c < 26; c++) {
nextPos[n][c] = -1;
}
// fill table by going backwards through s1
for (int i = n - 1; i >= 0; i--) {
for (int c = 0; c < 26; c++) {
nextPos[i][c] = nextPos[i + 1][c];
}
nextPos[i][s1[i] - 'a'] = i;
}
string ans = "";
int minLen = INT_MAX;
// try starting at each position in s1
for (int start = 0; start < n; start++) {
if (s1[start] != s2[0]) continue;
int idx = start;
bool ok = true;
// match s2 by jumping through nextPos
for (int j = 0; j < m; j++) {
if (idx == -1) {
ok = false;
break;
}
idx = nextPos[idx][s2[j] - 'a'];
if (idx == -1) {
ok = false;
break;
}
// move to next index for next char
idx++;
}
if (ok) {
int endIdx = idx - 1;
int len = endIdx - start + 1;
if (len < minLen) {
minLen = len;
ans = s1.substr(start, len);
}
}
}
return ans;
}
int main() {
string s1 = "abcdebdde";
string s2 = "bde";
cout << minWindow(s1, s2) << endl;
return 0;
}
import java.util.*;
class GfG {
public static String minWindow(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// nextPos[i][ch] : next occurrence of character
// ch after index i in s1
int[][] nextPos = new int[n + 2][26];
for (int c = 0; c < 26; c++) {
nextPos[n][c] = -1; // initialize last row with -1
}
// fill table by going backwards through s1
for (int i = n - 1; i >= 0; i--) {
for (int c = 0; c < 26; c++) {
nextPos[i][c] = nextPos[i + 1][c];
}
nextPos[i][s1.charAt(i) - 'a'] = i;
}
String ans = "";
int minLen = Integer.MAX_VALUE;
// try starting at each position in s1
for (int start = 0; start < n; start++) {
if (s1.charAt(start) != s2.charAt(0)) continue;
int idx = start;
boolean ok = true;
// match s2 by jumping through nextPos
for (int j = 0; j < m; j++) {
if (idx == -1) {
ok = false;
break;
}
idx = nextPos[idx][s2.charAt(j) - 'a'];
if (idx == -1) {
ok = false;
break;
}
// move to next index for next char
idx++;
}
if (ok) {
int endIdx = idx - 1;
int len = endIdx - start + 1;
if (len < minLen) {
minLen = len;
ans = s1.substring(start, start + len);
}
}
}
return ans;
}
public static void main(String[] args) {
String s1 = "abcdebdde";
String s2 = "bde";
System.out.println(minWindow(s1, s2));
}
}
def minWindow(s1, s2):
n = len(s1)
m = len(s2)
# nextPos[i][ch] : next occurrence of character
# ch after index i in s1
nextPos = [[-1] * 26 for _ in range(n + 2)]
# initialize last row with -1 (no occurrence beyond end)
for c in range(26):
nextPos[n][c] = -1
# fill table by going backwards through s1
for i in range(n - 1, -1, -1):
for c in range(26):
nextPos[i][c] = nextPos[i + 1][c]
nextPos[i][ord(s1[i]) - ord('a')] = i
ans = ""
minLen = float('inf')
# try starting at each position in s1
for start in range(n):
if s1[start] != s2[0]:
continue
idx = start
ok = True
# match s2 by jumping through nextPos
for j in range(m):
if idx == -1:
ok = False
break
idx = nextPos[idx][ord(s2[j]) - ord('a')]
if idx == -1:
ok = False
break
# move to next index for next char
idx += 1
if ok:
endIdx = idx - 1
length = endIdx - start + 1
if length < minLen:
minLen = length
ans = s1[start:start + length]
return ans
if __name__ == "__main__":
s1 = "abcdebdde"
s2 = "bde"
print(minWindow(s1, s2))
using System;
class GfG {
public static string minWindow(string s1, string s2) {
int n = s1.Length;
int m = s2.Length;
// nextPos[i][ch] : next occurrence of character
// ch after index i in s1
int[,] nextPos = new int[n + 2, 26];
for (int c = 0; c < 26; c++) {
nextPos[n, c] = -1; // initialize last row with -1
}
// fill table by going backwards through s1
for (int i = n - 1; i >= 0; i--) {
for (int c = 0; c < 26; c++) {
nextPos[i, c] = nextPos[i + 1, c];
}
nextPos[i, s1[i] - 'a'] = i;
}
string ans = "";
int minLen = int.MaxValue;
// try starting at each position in s1
for (int start = 0; start < n; start++) {
if (s1[start] != s2[0]) continue;
int idx = start;
bool ok = true;
// match s2 by jumping through nextPos
for (int j = 0; j < m; j++) {
if (idx == -1) {
ok = false;
break;
}
idx = nextPos[idx, s2[j] - 'a'];
if (idx == -1) {
ok = false;
break;
}
// move to next index for next char
idx++;
}
if (ok) {
int endIdx = idx - 1;
int len = endIdx - start + 1;
if (len < minLen) {
minLen = len;
ans = s1.Substring(start, len);
}
}
}
return ans;
}
public static void Main(string[] args) {
string s1 = "abcdebdde";
string s2 = "bde";
Console.WriteLine(minWindow(s1, s2));
}
}
function minWindow(s1, s2) {
let n = s1.length;
let m = s2.length;
// nextPos[i][ch] : next occurrence of character
// ch after index i in s1
let nextPos = Array.from({ length: n + 2 }, () => Array(26).fill(-1));
// initialize last row with -1 (no occurrence beyond end)
for (let c = 0; c < 26; c++) {
nextPos[n][c] = -1;
}
// fill table by going backwards through s1
for (let i = n - 1; i >= 0; i--) {
for (let c = 0; c < 26; c++) {
nextPos[i][c] = nextPos[i + 1][c];
}
nextPos[i][s1.charCodeAt(i) - 97] = i;
}
let ans = "";
let minLen = Infinity;
// try starting at each position in s1
for (let start = 0; start < n; start++) {
if (s1[start] !== s2[0]) continue;
let idx = start;
let ok = true;
// match s2 by jumping through nextPos
for (let j = 0; j < m; j++) {
if (idx === -1) {
ok = false;
break;
}
idx = nextPos[idx][s2.charCodeAt(j) - 97];
if (idx === -1) {
ok = false;
break;
}
// move to next index for next char
idx++;
}
if (ok) {
let endIdx = idx - 1;
let len = endIdx - start + 1;
if (len < minLen) {
minLen = len;
ans = s1.substring(start, start + len);
}
}
}
return ans;
}
// Driver Code
let s1 = "abcdebdde";
let s2 = "bde";
console.log(minWindow(s1, s2));
Output
bcde