Minimum Window Substring with Repeated Required Characters

Read the full interview experience this question came from →

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

|Home/Coding & Algorithms/Lyft
Lyft logo
Lyft
Sep 8, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

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

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...