mirror of
https://github.com/prdlk/leetcode.git
synced 2026-11-02 21:22:43 +00:00
56 lines
1.8 KiB
Plaintext
56 lines
1.8 KiB
Plaintext
---
|
|
title: '76. Minimum Window Substring'
|
|
description: Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string ""
|
|
icon: dot
|
|
topics:
|
|
- { name: "Hash Table", slug: "hash-table" }
|
|
- { name: "String", slug: "string" }
|
|
- { name: "Sliding Window", slug: "sliding-window" }
|
|
issue: "https://github.com/prdlk/leetcode/issues/57"
|
|
companies:
|
|
- { name: "Amazon", period: "Thirty Days", frequency: 55.9 }
|
|
- { name: "Lyft", period: "Three Months", frequency: 93.3 }
|
|
- { name: "Microsoft", period: "Three Months", frequency: 48.3 }
|
|
- { name: "Meta", period: "Three Months", frequency: 34.5 }
|
|
- { name: "Google", period: "Three Months", frequency: 23.9 }
|
|
- { name: "Oracle", period: "Six Months", frequency: 78.7 }
|
|
- { name: "Goldman Sachs", period: "Six Months", frequency: 44.8 }
|
|
- { name: "Bloomberg", period: "Six Months", frequency: 25.5 }
|
|
sidebar:
|
|
label: 'Minimum Window Substring'
|
|
badge: 'Hard'
|
|
---
|
|
|
|
::::warning
|
|
Could you find an algorithm that runs in O(m + n) time?
|
|
::::
|
|
|
|
### Example 1:
|
|
- Input: `s = "ADOBECODEBANC", t = "ABC"`
|
|
- Output: `"BANC"`
|
|
- Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string `t`.
|
|
|
|
### Example 2:
|
|
- Input: `s = "a", t = "a"`
|
|
- Output: `"a"`
|
|
- Explanation: The entire string `s` is the minimum window.
|
|
|
|
### Example 3:
|
|
- Input: `s = "a", t = "aa"`
|
|
- Output: `""`
|
|
- Explanation: Both 'a's from `t` must be included in the window. Since the largest window of `s` only has one 'a', return empty string.
|
|
|
|
### Constraints:
|
|
|
|
- `m == s.length`
|
|
- `n == t.length`
|
|
- `1 <= m, n <= 10^5`
|
|
- `s` and `t` consist of uppercase and lowercase English letters.
|
|
|
|
## Solution
|
|
|
|
```py
|
|
class Solution:
|
|
def minWindow(self, s: str, t: str) -> str:
|
|
```
|