Lv.3hashsliding-windowstringtwo-pointers
Minimum Window Substring
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| s | t | result |
|---|---|---|
"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
-
s.length,t.length, lowercase letters only
Expected complexity
- Time
- O(|s| + |t|)
- Space
- O(1)
Examples
| s | t | Expected |
|---|---|---|
"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 .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 8 | verdict only |
| performance | 60 | 4 | verdict only |