Quick Overview

Find the shortest substring covering every required character, including duplicates, with case-sensitive matching and a linear-time minimum-window algorithm.

Minimum Window Substring with Repeated Required Characters

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `minimum_window(s, t)` to return the shortest contiguous substring of `s` containing every character in `t` with at least its required multiplicity. Character matching is case-sensitive. Return the empty string if no such substring exists. Both strings contain only uppercase and lowercase English letters and have lengths from 1 through 100,000. Inputs with a valid minimum window have a unique answer; no tie-breaking rule needs to be invented. ### Examples ```text minimum_window("ADOBECODEBANC", "ABC") -> "BANC" minimum_window("a", "aa") -> "" ``` The first result includes all three required characters. The second input cannot supply the two occurrences of `a` required by `t`. Repeated target characters must be counted; checking only distinct-character membership is insufficient. Aim for time linear in the combined string lengths. Problem reference: [LeetCode 76](https://leetcode.com/problems/minimum-window-substring/).

Overview: Find the shortest substring covering every required character, including duplicates, with case-sensitive matching and a linear-time minimum-window algorithm.

Read the full Lyft Software Engineer interview experience this question came from

Implement `minimum_window(s, t)` to return the shortest contiguous substring of `s` containing every character in `t` with at least its required multiplicity. Character matching is case-sensitive. Return the empty string if no such substring exists. Both strings contain only uppercase and lowercase English letters and have lengths from 1 through 100,000. Inputs with a valid minimum window have a unique answer; no tie-breaking rule needs to be invented. ### Examples ```text minimum_window("ADOBECODEBANC", "ABC") -> "BANC" minimum_window("a", "aa") -> "" ``` The first result includes all three required characters. The second input cannot supply the two occurrences of `a` required by `t`. Repeated target characters must be counted; checking only distinct-character membership is insufficient. Aim for time linear in the combined string lengths. Problem reference: [LeetCode 76](https://leetcode.com/problems/minimum-window-substring/).

Constraints

  • Both s and t have lengths from 1 through 100000 inclusive.
  • Both strings contain only uppercase and lowercase English letters.
  • Matching is case-sensitive and every target multiplicity must be satisfied.
  • Return the shortest contiguous covering substring, or the empty string if none exists.
  • Whenever a minimum window exists, the input guarantees a unique answer.

Examples

Input: ('ADOBECODEBANC', 'ABC')

Expected Output: 'BANC'

Explanation: The first source example has the uniquely shortest window BANC.

Input: ('a', 'aa')

Expected Output: ''

Explanation: The second source example has insufficient target multiplicity.

Hints

  1. Repeated target characters each contribute to the required multiplicity.
  2. A window must remain contiguous, even when it contains unneeded letters.

Loading coding console...

Show the approach

Approach

Maintain need[c] as the target count of character c minus its count in the current window; negative values mean the window has excess copies. The missing counter is the total number of still-unsatisfied required occurrences. Extend the right edge by one character, reducing missing only when that character was still needed, then decrement its need value. Whenever missing reaches zero, the window covers the target. Record its length if it improves the best, then repeatedly remove the leftmost character: increase its need value and stop shrinking once an occurrence becomes missing. Whenever the current window is valid, shrinking examines its valid starts through the shortest valid form before the right edge advances. Any start removed earlier cannot yield a better future answer: extending its previously valid window only makes it longer, and it was already considered. The shortest recorded covering window is therefore globally optimal. Missing characters, insufficient multiplicities and case differences are handled by the same counts. The unique-answer promise means no extra tie rule is required. Both edges advance at most len(s) times, initialization reads t once, and a fixed ASCII count array is used. Only the final answer substring is copied.

Time complexity:
O(len(s) + len(t))
Space complexity:
O(1) auxiliary counting space for the fixed character domain, plus O(answer length) for the returned substring.