Katkat
Back

Smallest Covering Window in a String

LyftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests using the two-pointer sliding window pattern combined with frequency counting to find the shortest substring satisfying multiset inclusion constraints in linear time.

Smallest Covering Window in a String

Given two strings s and t, return the minimum length substring of s such that every character in t (including duplicate occurrences) is contained within that substring. If no such substring exists, return the empty string "".

If there are multiple covering windows of the same minimum length, return the one that begins at the smallest index.

Function Signature

def min_covering_window(s: str, t: str) -> str:
    pass

Constraints

  • 1 <= len(s), len(t) <= 10^5
  • s and t consist of uppercase and lowercase English letters ('a'-'z', 'A'-'Z').
  • The comparison is case-sensitive ('a' is not equal to 'A').

Examples

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The substring "BANC" contains 'A', 'B', and 'C'. Its length is 4, which is the shortest possible window covering all characters of t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string "a" covers t.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both characters in t must be present in the window. String s only has one 'a', so no valid window exists.

Edge Cases to Consider

  • len(t) > len(s): It is impossible to cover t, so return "" immediately.
  • Characters in t contain duplicates: The window must contain at least as many occurrences of each character as present in t.
  • t contains characters not present in s at all.

Hints

Hint 1

Start by building a frequency map of all characters in `t`, then use two pointers (`left` and `right`) to represent a sliding window over `s`.

Hint 2

Maintain a count of satisfied unique characters from `t` to determine whether the current window is valid in O(1) time.

Hint 3

Expand `right` until the window contains all needed characters, then advance `left` to shrink the window as much as possible while keeping it valid.

Follow-up questions

  • How would you optimize the search if `len(s)` is very large (e.g., 10^8) but characters matching `t` are extremely sparse?
  • How would the problem change if the characters of `t` were required to appear in `s` in the exact relative order (as a subsequence)?
  • Can you adapt this algorithm to process `s` as an unbounded stream where you cannot store the entire string in memory?