What is the time complexity of Minimum Window Substring?

The optimal solution has a time complexity of O(s).

What data structures are used to solve Minimum Window Substring?

This problem uses Hash Table, String, Sliding Window. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Minimum Window Substring?

Insight 1: Using a sliding window approach allows us to efficiently explore all possible substrings of 's' without redundant calculations. Insight 2: Employing a hash table (or counter) is crucial for tracking the frequency of characters in 't' and within the current window of 's'. This enables constant-time lookups and updates.

Which companies ask LeetCode 76. Minimum Window Substring in interviews?

This problem is frequently asked at Adobe, Agoda, Airbnb, Amazon, Apollo.io and 25 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimum Window Substring - LeetCode 76 Solution

Minimum Window Substring - Complete Solution Guide

Minimum Window Substring is LeetCode problem 76, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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" O

Detailed Explanation

The problem asks us to find the smallest substring within a larger string 's' that contains all the characters of another string 't', including any duplicate characters present in 't'. The substring must contain at least one occurrence of each character in 't' with the required frequency. If such a substring exists, we return it; otherwise, we return an empty string. The problem guarantees that the answer is unique if it exists.

Solution Approach

The solution uses a sliding window technique combined with hash tables. We maintain two pointers, 'l' (left) and 'r' (right), which define the boundaries of our sliding window within the string 's'. We expand the window by incrementing 'r' and shrink it by incrementing 'l'. A hash table `dict_t` stores the required character counts from string 't', and another hash table `window_counts` tracks the character counts within the current window. We iterate through 's', expanding the window. When the window contains all characters in 't' with sufficient frequency, we try to shrink the window from the left, updating the minimum window found so far. The process continues until the right pointer reaches the end of the string 's'.

Step-by-Step Algorithm

Step 1: Initialize two hash tables: `dict_t` to store the frequency of each character in string 't', and `window_counts` to track the frequency of characters in the current sliding window of 's'.
Step 2: Initialize two pointers, 'l' and 'r', to 0, representing the left and right boundaries of the sliding window.
Step 3: Initialize a variable `formed` to 0, to track how many characters in `dict_t` are fully satisfied within the current window.
Step 4: Initialize a tuple or array `ans` to store the length of the minimum window found so far, and the start and end indices of the minimum window.
Step 5: Iterate through string 's' with the right pointer 'r'.
Step 6: For each character encountered at 's[r]', update its count in `window_counts`.
Step 7: If the character at 's[r]' is present in `dict_t` and its count in `window_counts` matches its count in `dict_t`, increment `formed` by 1.
Step 8: While `l` <= `r` and `formed` equals the number of unique characters in `dict_t` (i.e., `required`), it means the current window is valid. Then, shrink the window from the left.
Step 9: Update the minimum window `ans` if the current window length is smaller than the previous minimum.
Step 10: Decrement the count of the character at 's[l]' in `window_counts`.
Step 11: If the character at 's[l]' is present in `dict_t` and its count in `window_counts` is now less than its count in `dict_t`, decrement `formed` by 1.
Step 12: Increment the left pointer 'l' by 1.
Step 13: Increment the right pointer 'r' by 1 to expand the window.
Step 14: After iterating through the entire string 's', if a valid window was found, return the corresponding substring; otherwise, return an empty string.

Key Insights

Insight 1: Using a sliding window approach allows us to efficiently explore all possible substrings of 's' without redundant calculations.
Insight 2: Employing a hash table (or counter) is crucial for tracking the frequency of characters in 't' and within the current window of 's'. This enables constant-time lookups and updates.
Insight 3: Maintaining a separate counter for characters in the current window allows us to check if we've satisfied the character requirements defined by 't'.

Complexity Analysis

Time Complexity: O(s)

Space Complexity: O(t)

Topics

This problem involves: Hash Table, String, Sliding Window.

Companies

Asked at: Adobe, Agoda, Airbnb, Amazon, Apollo.io, Apple, Bloomberg, ByteDance, Fastenal, Infosys, LinkedIn, Lyft, MakeMyTrip, Meta, Microsoft, Nagarro, Oracle, PayPal, Salesforce, Snap, Snowflake, SoFi, TikTok, Uber, Walmart Labs, Yahoo, Yandex, Zeta, Zopsmart, thoughtspot.

Minimum Window Substring | LeetCode 76

Hard

Hash Table String Sliding Window

Time: O(s)Space: O(t)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (t.isEmpty() || s.isEmpty()) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }

        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();

        int[] ans = {Integer.MAX_VALUE, -1, -1};

        while (r < s.length()) {
            char character = s.charAt(r);
            windowCounts.put(character, windowCounts.getOrDefault(character, 0) + 1);

            if (dictT.containsKey(character) && windowCounts.get(character).equals(dictT.get(character))) {
                formed++;
            }

            while (l <= r && formed == required) {
                int currentLen = r - l + 1;
                if (currentLen < ans[0]) {
                    ans[0] = currentLen;
                    ans[1] = l;
                    ans[2] = r;
                }

                char leftChar = s.charAt(l);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                if (dictT.containsKey(leftChar) && windowCounts.get(leftChar) < dictT.get(leftChar)) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == Integer.MAX_VALUE ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 76: Minimum Window Substring - Detailed explanation and solution approaches.

Topics

Hash Table String Sliding Window

Companies

AdobeAgodaAirbnbAmazonApollo.ioAppleBloombergByteDance

Stats

Difficulty:Hard

Languages:4

Companies:30

Problem #:76

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

14 steps

1
Step 1: Initialize two hash tables: `dict_t` to store the frequency of each character in string 't', and `window_counts` to track the frequency of characters in the current sliding window of 's'.
2
Step 2: Initialize two pointers, 'l' and 'r', to 0, representing the left and right boundaries of the sliding window.
3
Step 3: Initialize a variable `formed` to 0, to track how many characters in `dict_t` are fully satisfied within the current window.
4
Step 4: Initialize a tuple or array `ans` to store the length of the minimum window found so far, and the start and end indices of the minimum window.
5
Step 5: Iterate through string 's' with the right pointer 'r'.
6
Step 6: For each character encountered at 's[r]', update its count in `window_counts`.
7
Step 7: If the character at 's[r]' is present in `dict_t` and its count in `window_counts` matches its count in `dict_t`, increment `formed` by 1.
8
Step 8: While `l` <= `r` and `formed` equals the number of unique characters in `dict_t` (i.e., `required`), it means the current window is valid. Then, shrink the window from the left.
9
Step 9: Update the minimum window `ans` if the current window length is smaller than the previous minimum.
10
Step 10: Decrement the count of the character at 's[l]' in `window_counts`.
11
Step 11: If the character at 's[l]' is present in `dict_t` and its count in `window_counts` is now less than its count in `dict_t`, decrement `formed` by 1.
12
Step 12: Increment the left pointer 'l' by 1.
13
Step 13: Increment the right pointer 'r' by 1 to expand the window.
14
Step 14: After iterating through the entire string 's', if a valid window was found, return the corresponding substring; otherwise, return an empty string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(s)

💾

Space Complexity

O(t)

📝

Why?

The time complexity is determined by the dominant operations: iterating through string 's' using the sliding window, and creating the frequency map for string 't'. The space complexity is determined by the hash tables used to store character frequencies, which are proportional to the number of distinct characters in string 't'.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible substrings of 's' and check if each substring contains all the characters of 't'.

Time: O(m^3 * n), where m is the length of string s and n is the length of string t. Generating all substrings takes O(m^2) and checking each substring takes O(m * n) time.Space: O(n), for storing the frequency of characters in 't'.

Trade-offs: This approach is simple to understand but highly inefficient due to the high time complexity. It's not practical for large input strings. The sliding window approach is significantly better.

✨

Key Insights

1Insight 1: Using a sliding window approach allows us to efficiently explore all possible substrings of 's' without redundant calculations.
2Insight 2: Employing a hash table (or counter) is crucial for tracking the frequency of characters in 't' and within the current window of 's'. This enables constant-time lookups and updates.
3Insight 3: Maintaining a separate counter for characters in the current window allows us to check if we've satisfied the character requirements defined by 't'.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: If string 't' is empty, the function should return an empty string. The code correctly handles this case with the initial check `if not t or not s: return ""`.
Edge case 2: If string 's' does not contain all characters in 't', the function should return an empty string. The code correctly handles this scenario because if the `ans` variable remains unchanged (i.e., its initial value), it means no valid window was found.
Edge case 3: When 's' and 't' are equal and both have length 1 (e.g., s = 'a', t = 'a'), the entire string 's' is the answer. The sliding window algorithm correctly identifies this.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle duplicate characters in 't'. The solution must ensure that the window in 's' contains at least as many occurrences of each character as present in 't'. Failing to track character counts accurately leads to incorrect results.

✗Common mistake 2: Not shrinking the window optimally. After finding a valid window, it's crucial to shrink it from the left to find the minimum possible window. Incorrectly shrinking the window or failing to shrink it at all leads to a larger-than-necessary window.

✗Common mistake 3: Not considering edge cases where either 's' or 't' is empty.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text search engines use similar algorithms to find the smallest snippet of a document that contains all the query terms. This helps provide relevant search results to the user.

🏦Real-world scenario 2: In bioinformatics, finding the shortest DNA sequence containing a specific set of genes (represented by character strings) is a similar problem that can be solved using this algorithm.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Minimum Window Substring"?

For this hard-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?