Implement minimum window substring with counts
Company: DoorDash
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function min_window_with_counts(s: str, t: str) -> tuple[int,int] that returns the (start_index, end_index) of the shortest substring of s containing all characters in t with at least their required multiplicities. Constraints and rules:
- ASCII strings; case-sensitive; indices are 0-based; return (-1, -1) if no window exists.
- The window cannot skip characters; whitespace and punctuation in s count as normal characters.
- If multiple windows have the same minimal length, return the one with the smallest start index; if still tied, the one with the smallest end index.
- Time complexity must be O(n) and space O(Σ) using a sliding window and frequency maps; do not sort or use nested scans over s.
- You must handle large inputs (len(s) up to 2e6) without quadratic behavior.
Provide at least 3 test cases, including:
1) s = "ADOBECODEBANC", t = "ABC" -> expected (9, 12) for "BANC".
2) s = "aAaBbBc", t = "Aab" -> expected (0, 3) for "aAaB" (meets counts: A×2, a×1, b×1) or any equally minimal valid window following tie-breaking.
3) s = "xyzzzy", t = "zz" -> expected (2, 3). Explain how your code maintains counts and a satisfied counter.
Quick Answer: This question evaluates understanding of sliding-window algorithms, frequency/count maps, handling character multiplicities and case sensitivity in string processing, along with attention to tie-breaking by indices and linear-time/space constraints.
Implement `min_window_with_counts(s, t)` that returns the inclusive `(start_index, end_index)` of the shortest contiguous substring of `s` that contains every character of `t` with at least its required multiplicity.
Rules:
- ASCII strings; matching is case-sensitive ('b' != 'B'); indices are 0-based.
- The window is contiguous (you cannot skip characters); whitespace and punctuation count as normal characters.
- If `t` has repeated characters (e.g. "AABC"), the window must contain at least that many of each.
- Return `(-1, -1)` if no valid window exists, or if `t` is empty.
- If several windows share the minimal length, return the one with the smallest start index; if still tied, the smallest end index. (With a standard sliding window the first minimal window encountered already satisfies this.)
- Must run in O(n) time and O(Σ) space using a sliding window with frequency maps and a satisfied counter; no sorting, no nested scans over `s`. Inputs can be large (len(s) up to 2e6).
Examples:
1. s = "ADOBECODEBANC", t = "ABC" -> (9, 12) (substring "BANC").
2. s = "aAaBbBc", t = "Aab" -> (1, 4) (substring "AaBb"; the lowercase 'b' rules out the (0,3) window).
3. s = "xyzzzy", t = "zz" -> (2, 3) (substring "zz").
Constraints
- ASCII strings; matching is case-sensitive.
- 0-based, inclusive indices.
- Return (-1, -1) if no valid window exists or t is empty.
- len(s) can be up to 2e6 - must be O(n), no sorting or nested scans over s.
- Repeated characters in t require that many occurrences in the window.
- On a tie in length, prefer the smallest start index, then smallest end index.
Examples
Input: ("ADOBECODEBANC", "ABC")
Expected Output: (9, 12)
Explanation: The shortest window containing A, B and C is "BANC" at indices 9..12.
Input: ("aAaBbBc", "Aab")
Expected Output: (1, 4)
Explanation: Case-sensitive: need A x1, a x1, b x1. "AaBb" (indices 1..4) is the shortest window with all three; the (0,3) window "aAaB" lacks lowercase 'b'.
Input: ("xyzzzy", "zz")
Expected Output: (2, 3)
Explanation: need z x2. The first two z's form the shortest window at indices 2..3.
Input: ("abc", "d")
Expected Output: (-1, -1)
Explanation: 'd' never appears in s, so no window exists.
Input: ("", "a")
Expected Output: (-1, -1)
Explanation: Empty source string has no window.
Input: ("a", "a")
Expected Output: (0, 0)
Explanation: Single matching character is a window of length 1.
Input: ("aa", "aa")
Expected Output: (0, 1)
Explanation: need a x2; the whole string is the only window meeting the multiplicity.
Input: ("bba", "ab")
Expected Output: (1, 2)
Explanation: need a x1, b x1. "ba" at indices 1..2 is shorter than "bba" and is the first minimal window.
Hints
- Build a need map of required counts from t and let required = number of distinct chars in t.
- Expand a right pointer over s. Only track characters that appear in t; increment a satisfied counter `have` exactly when window[c] first reaches need[c].
- When have == required the window is valid; shrink from the left, recording the shortest window, and decrement `have` only when removing a char drops window[c] below need[c].