Coding

Minimum Window Subsequence

Asked at

Salesforce

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part. If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Input: s1 = "abcdebdde", s2 = "bde" Output: "bcde" **Explanation: ** "bcde" is the answer because it occurs before "bdde" which has the same length. "deb" is not a smaller window because the elements of s2 in the window must occur in order.

Input: s1 = "jmeqsiwvaovvnbstl", s2 = "u" Output: ""

Input: s1="fhhjkeejkdjjs", s2=”jkj”

1 <= s1.length <= 2 * 104
1 <= s2.length <= 100
s1 and s2 consist of lowercase English letters.

cpp

class Solution {
public:
    string minWindow(string s1, string s2) {
        // User code goes here
    }
};

java

class Solution {
    public String minWindow(String s1, String s2) {
        // User code goes here
        return "";
    }
}

python

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        # User code goes here

javascript

class Solution {
    minWindow(s1, s2) {
        // User code goes here
        return "";
    }
}

csharp

public class Solution
{
    public string MinWindow(string s1, string s2)
    {
        // User code goes here
    }
}

func minWindow(s1 string, s2 string) string {
    // User code goes here
}

Stuck? Show a way to structure it+

01Scan S forward to match T as a subsequence.
02When matched, walk backward to minimize that window.
03Record the best boundaries.
04Restart forward scanning after the minimized start.
05Return empty if no match.

Reference answer

Unlike minimum-window substring, characters of T need not be contiguous inside the window. Scan S forward with an index into T; whenever all of T is matched, walk a second pointer backward from the current end, matching T backward, to find the latest possible start for this same end. That backward pass makes the window minimal for its endpoint, so compare it with the global best. Resume the forward scan just after that start, reset the pattern pointer, and continue. This direct method is easy to explain and often accepted; worst-case time is O(|S|*|T|) with O(1) space. For tighter bounds, describe a DP where each pattern prefix tracks the earliest start of a subsequence ending at each S position.

Then expect these follow-ups

How does the DP formulation work?
Tests: string DP
How would you return all minimum ties?
Tests: result handling

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question