DevExCode

LeetCode 76: Minimum Window Substring Solution

Master LeetCode problem 76 (Minimum Window Substring), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

76. Minimum Window Substring

Hard
Hash TableStringSliding Window

Problem Explanation

Explanation:

To solve this problem, we can use the sliding window technique. We will maintain two pointers, left and right, that define the current window. We will also maintain a hashmap to keep track of the characters in string t and their counts. The idea is to expand the window by moving the right pointer until we have a valid window that contains all the characters in string t. Once we have a valid window, we will try to minimize it by moving the left pointer and updating the minimum window length.

Here are the steps:

  1. Initialize a hashmap targetMap to store the character frequencies in string t.
  2. Initialize a hashmap windowMap to store the character frequencies in the current window.
  3. Initialize left and right pointers to 0.
  4. Iterate through the string s using the right pointer:
    • Update the windowMap with the character at index right.
    • Check if the current window contains all the characters in t.
      • If yes, move the left pointer to minimize the window.
    • Update the minimum window length if a valid window is found.
  5. Repeat step 4 until the right pointer reaches the end of string s.
  6. Return the minimum window substring found.

Time Complexity: O(m + n), where m is the length of string s and n is the length of string t. Space Complexity: O(n), where n is the length of string t.

:

Solution Code

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        
        Map<Character, Integer> targetMap = new HashMap<>();
        Map<Character, Integer> windowMap = new HashMap<>();
        
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }
        
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        int requiredChars = targetMap.size();
        int formedChars = 0;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            
            if (targetMap.containsKey(c) && windowMap.get(c).intValue() == targetMap.get(c).intValue()) {
                formedChars++;
            }
            
            while (left <= right && formedChars == requiredChars) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                char leftChar = s.charAt(left);
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                
                if (targetMap.containsKey(leftChar) && windowMap.get(leftChar) < targetMap.get(leftChar)) {
                    formedChars--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 76 (Minimum Window Substring)?

This page provides optimized solutions for LeetCode problem 76 (Minimum Window Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 76 (Minimum Window Substring)?

The time complexity for LeetCode 76 (Minimum Window Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 76 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 76 in Java, C++, or Python.

Back to LeetCode Solutions