Funcia
Lv.3hashsliding-windowstringtwo-pointers

Minimum Window Substring

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Return the length of the shortest substring of s that contains every letter of t with multiplicity ("aab" needs two a and one b), or 0 if none exists.

Examples

stresult
"adobecodebanc""abc"4
"a""aa"0
"aaflslflsldkalskaaa""aaa"3

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s: string, t: string) → int

Constraints

  • 1≤1 \le s.length, t.length ≤500,000\le 500{,}000, lowercase letters only

Expected complexity

Time
O(|s| + |t|)
Space
O(1)

Examples

stExpected
"adobecodebanc""abc"4
"a""aa"0
"aaflslflsldkalskaaa""aaa"3

Hint

Hint

Sliding window: grow the right end, track how many required letters are still missing, and when none are, shrink the left end as far as possible while recording the length. Each pointer moves forward once. Extending from every start is O(∣s∣2)O(|s|^2).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.