76. Minimum Window Substring
Minimum Window Substring (LeetCode 76) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
- Blind 75 · #15 of 75 · Sliding Window
- NeetCode 150 · #19 of 150 · Sliding Window
- NeetCode 250 · #43 of 250 · Sliding Window
How to solve Minimum Window Substring
Minimum Window Substring is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Use two pointers to create a window of letters in s, which would have all the characters from t.
- Expand the right pointer until all the characters of t are covered.
- Once all the characters are covered, move the left pointer and ensure that all the characters are still covered to minimize the subarray size.
The reference solution runs in O(n) time and O(k) space.
The Minimum Window Substring solution and editorial walks through the full approach with reference code.
Problem statement
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 "".
The testcases will be generated such that the answer is unique.
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 <= 105
- s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Topics and companies
Topics: Hash Table, String, Sliding Window.
Reported in interviews at Adobe, Airbnb, Amazon, Apple, Bloomberg, ByteDance, Facebook, Goldman Sachs, Google, LinkedIn, Lyft, Microsoft and others.
How to practise Minimum Window Substring on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(k) space.
Open Minimum Window Substring in the code editor, or read the Minimum Window Substring editorial for a worked solution with its approach and complexity analysis.
Where Minimum Window Substring sits in the DSA pattern sheet
Problems related to Minimum Window Substring
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Minimum Window Substring FAQ
What is the LeetCode number of Minimum Window Substring?
Minimum Window Substring is LeetCode problem 76, rated Hard.
What pattern is used to solve Minimum Window Substring?
Minimum Window Substring is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Minimum Window Substring?
The reference solution runs in O(n) time and O(k) space.
Which companies ask Minimum Window Substring?
Minimum Window Substring has been reported in interviews at Adobe, Airbnb, Amazon, Apple, Bloomberg, ByteDance, Facebook, Goldman Sachs, Google, LinkedIn, Lyft, Microsoft and others.