178. Ordered Cover Window
A radio operator receives a long string s of letters and is waiting for a secret call sign t. The call sign is heard whenever its letters occur in s in the same order, though other letters may be mixed in between (that is, t is a subsequence of the heard stretch).
Return the shortest contiguous substring of s that has t as a subsequence. If several shortest substrings exist, return the one that starts furthest to the left. If no substring works, return the empty string.
Example 1
- Input:
- s = "xabcbdacd", t = "abd"
- Output:
- "abcbd"
- Explanation:
The substring abcbd (indices 1 to 5) contains a, b, d in that order, and no shorter substring does: the only a before the d at index 5 sits at index 1, and the stretch starting at index 6 (acd) has no b. The answer is abcbd.
Example 2
- Input:
- s = "aabbaab", t = "ab"
- Output:
- "ab"
- Explanation:
The substring ab appears at indices 1 to 2, which is as short as any possible window (length 2). The later ab at indices 5 to 6 has the same length, but the leftmost one is returned.
Example 3
- Input:
- s = "abc", t = "d"
- Output:
- ""
- Explanation:
The letter d never appears, so the answer is the empty string.
Constraints
1 ≤ s.length ≤ 2 * 104
1 ≤ t.length ≤ 100
s and t consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(|s| * |t|)
- Space
- O(|t|)