Posted inLeetCode 75

LeetCode 76: Minimum Window Substring – Sliding Window Solution in C++, Java, Python & C#

No Comments
LeetCode 76: Minimum Window Substring

What Is the Minimum Window Substring?

The Minimum Window Substring problem asks:

Given two strings s and t, find the smallest substring of s that contains all characters of t (including duplicates). If no such substring exists, return "". citeturn0search2

This challenge tests your mastery of the sliding window pattern combined with hash‑based frequency tracking to achieve an optimal time complexity of O(S + T).

Solution Approach: Sliding Window + Frequency Maps

  1. Initialize Frequency Maps
    • Build targetMap for string t: counts of each character.
    • Maintain windowMap for the current window in s.
  2. Expand & Contract Window
    • Expand: Move the right pointer to include new characters; update windowMap.
    • Check: When the window covers all required chars (formed == required), attempt to contract by moving the left pointer to shrink the window while still satisfying the requirement.
  3. Track Minimum Window
    • Whenever a valid window is found, compare its length to the best so far.
    • Record the start index and length if it’s smaller.
  4. Return Result
    • If minLen was updated, return the corresponding substring; otherwise, return "".

Java Implementation

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

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray())
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);

        Map<Character, Integer> windowMap = new HashMap<>();
        int required = targetMap.size(), formed = 0;
        int left = 0, right = 0, minLen = Integer.MAX_VALUE, start = 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()) {
                formed++;
            }

            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                char d = s.charAt(left++);
                windowMap.put(d, windowMap.get(d) - 1);
                if (targetMap.containsKey(d) && 
                    windowMap.get(d) < targetMap.get(d)) {
                    formed--;
                }
            }
            right++;
        }
        return (minLen == Integer.MAX_VALUE) ? "" : s.substring(start, start + minLen);
    }
}

C++ Implementation

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> target, window;
        for (char c : t) target[c]++;
        int required = target.size(), formed = 0;
        int l = 0, r = 0, minLen = INT_MAX, start = 0;

        while (r < s.size()) {
            char c = s[r++];
            window[c]++;
            if (target.count(c) && window[c] == target[c])
                formed++;

            while (l < r && formed == required) {
                if (r - l < minLen) {
                    minLen = r - l;
                    start = l;
                }
                char d = s[l++];
                window[d]--;
                if (target.count(d) && window[d] < target[d])
                    formed--;
            }
        }
        return (minLen == INT_MAX) ? "" : s.substr(start, minLen);
    }
};

Python Implementation

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = Counter(t)
        window = Counter()
        required = len(target)
        formed = 0
        l = 0
        min_len = float('inf')
        start = 0

        for r, char in enumerate(s):
            window[char] += 1
            if char in target and window[char] == target[char]:
                formed += 1

            while l <= r and formed == required:
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    start = l
                window[s[l]] -= 1
                if s[l] in target and window[s[l]] < target[s[l]]:
                    formed -= 1
                l += 1

        return "" if min_len == float('inf') else s[start:start + min_len]

C# Implementation

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    public string MinWindow(string s, string t) {
        var target = new Dictionary<char,int>();
        foreach (var c in t)
            target[c] = target.GetValueOrDefault(c) + 1;

        var window = new Dictionary<char,int>();
        int required = target.Count, formed = 0;
        int l = 0, minLen = int.MaxValue, start = 0;

        for (int r = 0; r < s.Length; r++) {
            char c = s[r];
            window[c] = window.GetValueOrDefault(c) + 1;
            if (target.ContainsKey(c) && window[c] == target[c])
                formed++;

            while (l <= r && formed == required) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                char d = s[l++];
                window[d]--;
                if (target.ContainsKey(d) && window[d] < target[d])
                    formed--;
            }
        }
        return minLen == int.MaxValue ? "" : s.Substring(start, minLen);
    }
}

Complexity Analysis

  • Time Complexity: O(|s| + |t|) — each character in s and t is processed a constant number of times.
  • Space Complexity: O(|s| + |t|) — worst‑case storage in the hash maps.

The Minimum Window Substring algorithm (LeetCode 76) has several real-world applications, especially in areas where substring search, pattern matching, and efficient data parsing are important. Here are some real-time use cases:

🔍 1. Search Engines (Keyword Matching)

When a user types a query, search engines may look for the shortest snippet of text from a webpage or document that contains all search terms.
Use case:

Finding the shortest relevant passage in a document containing all user-entered keywords.

📚 2. Document Scanning and Highlighting

In software like PDF readers or online editors, when searching for multiple words, you want to highlight the smallest section containing all of them. Use case:

Highlighting a short paragraph in a long document that mentions all search terms.

🧬 3. DNA Sequence Analysis

In bioinformatics, researchers often need to find the shortest DNA sequence that contains a given set of markers (genes or proteins). Use case:

Locating the smallest DNA fragment with all necessary base patterns for a study.

🤖 4. Chatbots and NLP (Natural Language Processing)

In language understanding, a bot might need to find the minimum sentence or phrase in a message that matches a set of required tokens (like intents or keywords). Use case:

Extracting the smallest section of text that can be used to trigger a specific bot intent.

🛒 5. E-commerce Product Filtering

When matching user-selected filters (like “blue”, “cotton”, “shirt”), the system can search descriptions for the smallest product blurb that includes all attributes. Use case:

Displaying the most concise product detail that meets all chosen features.

📈 6. Log Monitoring and Alert Systems

Monitoring tools need to find the smallest time window in logs that show all key error events or messages for efficient debugging. Use case:

Isolating the shortest period in logs where all alerting conditions were triggered.

🗂 7. Data Compression and Optimization

For certain optimization problems, like reducing redundancy in text storage, finding compact segments with all required elements is useful. Use case:

Minimizing storage for blocks that contain a complete set of tokens or terms.

🧾 8. Auto-summarization Tools

Summarization tools may use this algorithm to extract the most relevant portion of a paragraph that includes all key ideas. Use case:

Creating a summary by extracting the smallest segment with all important terms.

These examples show that while the algorithm is taught in coding interviews, its logic is extremely useful in real-world data-heavy applications. Want me to generate real example code for one of these cases?

❓ FAQ: Minimum Window Substring (LeetCode 76)

🔹 Q1: What is the Minimum Window Substring problem?

A: It’s a classic string problem where you need to find the smallest substring in a given string s that contains all characters from another string t (including duplicates), in any order.

🔹 Q2: What type of algorithm is used to solve this problem efficiently?

A: The sliding window technique combined with a hash map for character frequency is used. This ensures the solution runs in linear time, O(S + T), where S and T are the lengths of the two strings.

🔹 Q3: Why is this problem important in interviews?

A: It tests multiple key concepts: string manipulation, two-pointer strategy, map-based frequency counting, and real-time window resizing—all commonly used in complex algorithmic problems.

🔹 Q4: What are real-world applications of this algorithm?

A: It’s used in:

  • Search engines (highlighting relevant snippets)
  • Document scanning tools
  • Bioinformatics (DNA sequence analysis)
  • Chatbots/NLP (intent detection)
  • Log monitoring systems
  • Product filtering on e-commerce platforms

👉 View real-world use cases above

🔹 Q5: How is this different from finding substrings with unique characters?

A: In this problem, duplicate characters in t must also be matched, meaning you must account for character counts, not just their presence.

🔹 Q6: Can this solution be implemented in multiple languages?

A: Yes! The algorithm is language-independent. We’ve included implementations in:

  • ✅ Java
  • ✅ Python
  • ✅ C++
  • ✅ C#

👉 Scroll up for complete multi-language code

🔹 Q7: What happens if no such window exists?

A: The function returns an empty string "" if it can’t find a window containing all characters from t.

🔹 Q8: How do we handle uppercase and lowercase letters?

A: By default, the algorithm is case-sensitive. If case-insensitivity is required, you should convert both strings to the same case (.toLowerCase() or .toUpperCase()).

🔹 Q9: What are the edge cases to consider?

A: Common edge cases include:

  • Empty strings s or t
  • t longer than s
  • All characters of t are the same
  • Characters in t not present in s

🔹 Q10: Can this algorithm handle Unicode characters?

A: Yes, as long as your programming language’s string and map structures support Unicode (which Java, Python, C#, and C++ do), the logic works.

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *