Katkat
Back

Minimum Window Substring with Repeated Required Characters

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests the sliding window technique and frequency counting to find the shortest substring containing all required characters with their exact multiplicities in linear time.

Problem Statement

Given two strings s and target, return the shortest contiguous substring in s that contains every character in target, including duplicate characters. Matching is case-sensitive.

If no such substring exists, return an empty string "".

If there are multiple substrings of the minimum length that satisfy the condition, return the one that appears earliest in s.

Your algorithm should achieve O(len(s) + len(target)) time complexity.

Function Signature

def min_window(s: str, target: str) -> str:
    pass

Constraints

  • 1 <= len(s), len(target) <= 10^5
  • s and target consist of uppercase and lowercase English letters ([a-zA-Z]).

Examples

Example 1

Input: s = "ADOBECODEBANC", target = "ABC"
Output: "BANC"
Explanation: Substrings like "ADOBEC" contain 'A', 'B', and 'C', but "BANC" has length 4, which is the shortest valid substring.

Example 2

Input: s = "a", target = "aa"
Output: ""
Explanation: 'a' appears twice in target, but only once in s. No valid window exists.

Example 3

Input: s = "aaFLyftXyfa", target = "aLy"
Output: "aaFLy"
Explanation: Matching is case-sensitive, so the substring must contain lowercase 'a', uppercase 'L', and lowercase 'y'.

Edge Cases

  • len(target) > len(s): Immediately return "".
  • target requires multiple copies of the same character (e.g., target = "AAB").
  • Exact match where s == target.

Hints

Hint 1

Use a two-pointer sliding window where the right pointer expands the window until all character requirements from target are satisfied.

Hint 2

Maintain a frequency map of target characters and a counter of how many unique characters currently meet their required count.

Hint 3

Once the window is valid, contract the left pointer as much as possible while maintaining validity, updating your minimum length record before the window becomes invalid again.

Follow-up questions

  • How would you optimize the approach if len(s) is very large (e.g., millions of characters) but target only contains a small set of distinct characters?
  • How would you adapt the solution if the input `s` is an infinite stream of characters rather than an in-memory string?
  • Suppose each character in target has an allowed tolerance (e.g., can be satisfied by matching case-insensitively with a penalty). How does that change the state tracking?