Katkat
Back

Shortest Substring Containing Every Character of a Pattern

LinkedInSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Return the shortest substring of a string that contains every character of a pattern with matching multiplicity, case-sensitively, choosing the leftmost substring on ties and an empty string when none exists. Tests efficient substring search and careful character-count bookkeeping.

Given two strings s and t, return the shortest contiguous substring of s that contains every character of t, counting repeats: if a character appears m times in t, the substring must contain it at least m times. Characters are case-sensitive. If no such substring exists, return the empty string.

Function Signature

def min_window(s: str, t: str) -> str:

Rules

  • The substring may contain characters that do not occur in t, and extra copies of characters that do.
  • If several substrings share the minimum length, return the one that starts at the smallest index of s.
  • Return "" when s has no qualifying substring, for example when t is longer than s.

Constraints

  • 1 <= len(s) <= 10^5
  • 1 <= len(t) <= 10^5
  • s and t consist of uppercase and lowercase English letters.

Examples

Example 1

  • Input: s = "XAYBZAXB", t = "ABX"
  • Output: "AXB"
  • Explanation: "XAYB" and "BZAX" also contain A, B and X, but they have length 4. "AXB", starting at index 5, has length 3, and no other substring of length 3 qualifies.

Example 2

  • Input: s = "cabwba", t = "ab"
  • Output: "ab"
  • Explanation: "ab" (starting at index 1) and "ba" (starting at index 4) both have length 2; the one that starts earlier is returned.

Example 3

  • Input: s = "Aa", t = "AA"
  • Output: ""
  • Explanation: t needs two uppercase A characters, s has only one, and the lowercase a does not count.