PPractick

The problem

A log-forensics tool looks for the shortest contiguous stretch of a log in which a given sequence of events T happens in order, with other events possibly in between. That's a window of S that contains T as a subsequence. Return the shortest such window, the leftmost one if several tie, or "" if none exists. A forward scan finds the earliest end where T is completed. A backward scan from that end, matching T in reverse, finds the latest possible start, which gives the tightest window ending there. Then search again starting just after that start.

Example: S = "abcdebdde", T = "bde" → "bcde".

Function signature

string minWindowSubsequence(const string& S, const string& T);  // T non-empty; "" if none

Test cases

Input (S, T)	Output	Explanation
("abcdebdde", "bde")	"bcde"	"bdde" is also length 4 but starts later
("abdbca", "ba")	"bca"
("aaa", "aa")	"aa"	Leftmost of the ties
("xyz", "zy")	""	Order matters
("abc", "abc")	"abc"

(Confirm: T must appear as a subsequence (in order, gaps allowed) inside a contiguous window of S; ties go to the leftmost window.)

How interviewers phrase it

• "Given strings S and T, find the minimum contiguous substring W of S such that T is a subsequence of W" (LeetCode 727).

Clarifying questions to ask

1. Subsequence (order matters, gaps allowed), not just the multiset of characters? (Yes, which is why the minimum-window-substring technique doesn't apply.)
2. How are ties broken? (Leftmost.)
3. What are the sizes? (|S| up to 2·10⁴, |T| up to 100.)

Follow-ups to expect

1. "Why the backward scan?"
2. "Why restart at s + 1?"
3. "What's the complexity?"
4. "DP alternative?"
5. "How is this different from Minimum Window Substring?"

Related questions

• Longest Repeating Character Replacement Hard
• Number of Substrings Containing All Three Characters Hard
• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard
• Count Number of Substrings Easy
• Longest Substring Without Repeating Characters Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in