Topics › Sliding Window and Two Pointers › Hard Problems

Minimum Window Subsequence

Hard TUF ID 754 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two strings s1 (length n) and s2 (length m). Find the shortest substring W of s1 such that s2 is a subsequence of W, that is, the characters of s2 appear in W in the same order, though not necessarily next to each other. If several shortest windows exist, return the one that starts furthest to the left. If there is none, return "".

This differs from Minimum Window Substring in one crucial way: order matters. For s2 = "bde", the window must contain a b, then later a d, then later an e.

Constraints: 1 ≤ n ≤ 2 × 10^4, 1 ≤ m ≤ 100, lowercase letters.

Example 1

s1 = "abcdebdde", s2 = "bde"
answer = "bcde"     // "bdde" is also length 4, but "bcde" starts earlier

Example 2

s1 = "geeksforgeeks", s2 = "eksrg"
answer = "eksforg"  // e, k, s, then r (in "for"), then g

Example 3

s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
answer = ""         // s1 has no 'u'

Approach 1: Brute force, greedy match from every start

Intuition. A window must start at a character equal to s2[0] (otherwise we could drop its first character and keep a valid, shorter window). Fix such a start i and match s2 greedily to the right, taking each character of s2 at its earliest possible position. Greedy matching finishes as early as any matching can, so it gives the shortest window that starts at i. Keep the shortest over all starts; scanning starts from left to right and replacing only on a strictly shorter window gives the leftmost answer on ties.

One extra observation lets us stop early: if s2 cannot be completed from start i, it cannot be completed from any later start either, because a later start sees a suffix of the same text.

Algorithm.

For each i with s1[i] == s2[0]:
- Walk p from i, advancing j in s2 whenever s1[p] == s2[j], until j == m or p == n.
- If j < m, stop the whole search. Otherwise the window is s1[i..p-1]; keep it if it is strictly shorter.
Return the best window or "".

static String bruteForce(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    if (m == 0) return "";
    int bestStart = -1, bestLen = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        if (s1.charAt(i) != s2.charAt(0)) continue;
        int j = 0, p = i;
        while (p < n && j < m) {                   // greedy: take each s2 character as early as possible
            if (s1.charAt(p) == s2.charAt(j)) j++;
            p++;
        }
        if (j < m) break;                          // s2 cannot be finished from here, nor from any later start
        if (p - i < bestLen) {                     // window is s1[i..p-1]
            bestLen = p - i;
            bestStart = i;
        }
    }
    return bestStart == -1 ? "" : s1.substring(bestStart, bestStart + bestLen);
}

Complexity. Time O(n^2): up to n starts, each scanning up to n characters. Space O(1).

The wasted work: windows from neighbouring starts overlap heavily, and each scan re-walks most of the same text.

Approach 2: Better, forward then backward two pointers

Intuition. Instead of fixing the start, find an end first. Scan forward from the current position, matching s2 greedily, until the last character of s2 is matched at index end. Now we know a window ending at end exists, but its start may be too early: the forward scan took the first s2[0] it saw, and a later one might also work. So walk backward from end, matching s2 from its last character to its first. The backward greedy match finds the latest possible start for a window ending at end, which is the shortest window with that end.

Then restart the forward scan at start + 1. Any better window must begin strictly after start: a window starting at or before start and ending after end contains the window we just found, so it cannot be shorter.

Algorithm.

i = 0.
Forward: advance i, matching s2 left to right, until j == m (then end = i) or i == n (then stop).
Backward: from end, match s2 right to left while moving i left; when all of s2 is matched, start = i + 1.
Record s1[start..end] if strictly shorter. Set i = start + 1 and repeat.

static String twoPointers(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    if (m == 0) return "";
    int bestStart = -1, bestLen = Integer.MAX_VALUE;
    int i = 0;
    while (i < n) {
        int j = 0;
        while (i < n) {                            // forward: find where s2 is completed
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
                if (j == m) break;
            }
            i++;
        }
        if (i == n) break;                         // s2 cannot be completed any more
        int end = i;
        j = m - 1;
        while (j >= 0) {                           // backward: match s2 from its last character
            if (s1.charAt(i) == s2.charAt(j)) j--;
            i--;
        }
        int start = i + 1;                         // latest start whose window ends at 'end'
        if (end - start + 1 < bestLen) {
            bestLen = end - start + 1;
            bestStart = start;
        }
        i = start + 1;                             // next window must start strictly later
    }
    return bestStart == -1 ? "" : s1.substring(bestStart, bestStart + bestLen);
}

Dry run on s1 = "abcdebdde", s2 = "bde":

round	forward from	end found	backward gives start	window	best
1	0	4 (`e`)	1 (`b`)	“bcde”	“bcde”
2	2	8 (`e`)	5 (`b`)	“bdde” (tie, not stored)	“bcde”
3	6	none			“bcde”

Complexity. Time O(n^2) in the worst case, because consecutive rounds can rescan overlapping stretches; on most inputs it is much faster than the brute force. Space O(1).

Approach 3: Optimal, dynamic programming on the latest start

Intuition. Process s1 left to right, one index i at a time, and maintain for every prefix of s2 the answer to: “what is the latest start p such that s2[0..j] is a subsequence of s1[p..i]?” Call it start[j] (or -1 if impossible). The latest start is what we want, because for a fixed end, a later start means a shorter window. Then start[m-1] at index i gives the shortest window ending at i.

The update when we read c = s1[i]:

If s2[0] == c, then s2[0..0] can start right here: start[0] = i (the latest possible).
If s2[j] == c for j > 0, we can finish s2[0..j] at i by extending the best match of s2[0..j-1] that ends before i: start[j] = start[j-1].
If s2[j] != c, nothing changes: the best window for s2[0..j] stays the one we had.

The order of updates matters. start[j-1] must describe s1[..i-1], not include the character we are reading right now, otherwise a single character of s1 could be used for two consecutive characters of s2. Iterating j from m - 1 down to 0 reads start[j-1] before it is overwritten for index i. This is the same reason 0/1 knapsack iterates its 1D table from right to left.

Algorithm.

start[0..m-1] = -1.
For each i: for j = m - 1 down to 0, if s2[j] == s1[i], set start[j] = (j == 0) ? i : start[j-1].
If start[m-1] != -1 and i - start[m-1] + 1 is strictly smaller than the best, record it.
Return the best window or "".

static String optimal(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    if (m == 0) return "";
    int[] start = new int[m];                      // start[j]: latest p with s2[0..j] a subsequence of s1[p..i], or -1
    Arrays.fill(start, -1);
    int bestStart = -1, bestLen = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        char c = s1.charAt(i);
        for (int j = m - 1; j >= 0; j--) {         // right to left so start[j - 1] still refers to s1[..i-1]
            if (s2.charAt(j) == c) start[j] = (j == 0) ? i : start[j - 1];
        }
        if (start[m - 1] != -1 && i - start[m - 1] + 1 < bestLen) {
            bestLen = i - start[m - 1] + 1;
            bestStart = start[m - 1];
        }
    }
    return bestStart == -1 ? "" : s1.substring(bestStart, bestStart + bestLen);
}

Dry run on s1 = "abcdebdde", s2 = "bde" (start shown after each index):

i	char	start[b], start[d], start[e]	window ending at i	best
1	b	1, -1, -1
3	d	1, 1, -1
4	e	1, 1, 1	“bcde” (1..4)	“bcde”
5	b	5, 1, 1	“bcdeb” (1..5)	“bcde”
6	d	5, 5, 1	longer	“bcde”
8	e	5, 5, 5	“bdde” (5..8), a tie	“bcde”

Indices 0, 2 and 7 change nothing that matters (7 re-sets start[d] to 5).

Complexity. Time O(n · m): m constant-time updates per character of s1, about 2 × 10^6 steps at the limits, with no bad worst case. Space O(m) for the start array. Recording only on a strictly shorter window keeps the leftmost answer, because among windows of equal length the one with the smaller end also has the smaller start, and ends are visited in increasing order.

Edge cases and pitfalls

No match. If some character of s2 never appears in s1 (or appears too few times, as in s1 = "a", s2 = "aa"), return "".
Ties. Return the leftmost shortest window: "bcde", not "bdde". Update the best only on a strictly smaller length.
Order matters. s2 = "ba" is not satisfied by "ab". Using character counts (as in Minimum Window Substring) solves a different problem.
One character of s1 used twice. In the DP, iterating j upward would let s1[i] match both s2[j-1] and s2[j] when they are equal, as in s2 = "mm". The test "cnhczmccqouqadqtmjjzl", "mm" (answer "mccqouqadqtm") catches that bug.
Restart point in Approach 2. Restart at start + 1, not at end + 1; the next shortest window can overlap the current one.

Minimum Window Substring asks for the shortest window containing the characters of t in any order.
Longest common subsequence is the classic subsequence DP between two strings.
Distinct subsequences counts the ways one string occurs as a subsequence of another, with a similar right-to-left 1D update.
Longest Substring Without Repeating Characters is a simpler window over a single string.

Minimum Window Subsequence

Problem

Approach 1: Brute force, greedy match from every start

Approach 2: Better, forward then backward two pointers

Approach 3: Optimal, dynamic programming on the latest start

Edge cases and pitfalls

Related problems