Smallest Window Containing All Characters of Another String

Implement smallestWindowContainingAllChars

Given two strings s and t, return the shortest contiguous substring of s that contains every character of t (including repeats — if t has two 'a's, the window needs at least two). If no such window exists, return an empty string. Unlike a fixed-size window, this window's size isn't known in advance — it has to grow and shrink as the scan progresses. The sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. technique tracks a frequency count of the window's characters alongside a formed counter — how many of t's distinct characters are currently satisfied. Grow the window right until formed reaches the required count, then greedily shrink from the left — recording the shortest valid window at every step — until a character falls short again. Every character is visited once by each pointer, so the whole scan runs in O(n).

Example 1:

Input: s = "aabec", t = "abc"

Output: "abec"

Example 2:

Input: s = "adobecodebanc", t = "abc"

Output: "banc"

Example 3:

Input: s = "a", t = "a"

Output: "a"

+ 8 hidden test cases run on Submit.

Constraints:

  • 1 ≤ s.length, t.length ≤ 10⁵
  • s and t consist of lowercase English letters only
  • t.length ≤ s.length

s =

aabec

t =

abc