Minimum Window Substring - Practice Coding Problems

Minimum Window Substring - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "ADOBECODEBANC", t = "ABC"

› Output: "BANC"

💡 Note: The minimum window substring "BANC" includes one 'A', one 'B', and one 'C' from t.

Example 2 — No Valid Window

$ Input: s = "a", t = "aa"

› Output: ""

💡 Note: String s only has one 'a', but t requires two 'a's. No valid window exists.

Example 3 — Entire String

$ Input: s = "a", t = "a"

› Output: "a"

💡 Note: The minimum window is the entire string s, which is "a".

Constraints

1 ≤ s.length, t.length ≤ 10⁵
s and t consist of uppercase and lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Source string s and target string t with required characters

Process

Find minimum window in s containing all characters from t

Output

Return shortest valid substring or empty string

Key Takeaway

🎯 Key Insight: Use sliding window with hash maps to efficiently track character frequencies while maintaining minimum valid window

Asked in

f Facebook 85 a Amazon 72 M Microsoft 68 G Google 65 🍎 Apple 45

The sliding window approach is optimal for this problem. The key insight is to use two pointers to maintain a dynamic window that expands when invalid and contracts when valid. Best approach uses hash maps to track character frequencies. Time: O(m + n), Space: O(m + n).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Hash Map	O(m + n)	O(m + n)	Use two pointers to maintain a sliding window that expands and contracts
Brute Force - Check All Substrings	O(m² × n)	O(m + n)	Check every possible substring to find the minimum window

Sliding Window with Hash Map — Algorithm Steps

Count character frequencies in string t
Use left and right pointers to maintain a sliding window
Expand right pointer until window contains all characters from t
Contract left pointer while maintaining validity to find minimum window

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Move right pointer to include more characters

Contract Window

Move left pointer when window is valid

Track Minimum

Record the smallest valid window found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char* solution(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    
    if (sLen == 0 || tLen == 0 || sLen < tLen) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    int tCount[256] = {0};
    int uniqueChars = 0;
    
    for (int i = 0; i < tLen; i++) {
        if (tCount[(int)t[i]] == 0) {
            uniqueChars++;
        }
        tCount[(int)t[i]]++;
    }
    
    int windowCounts[256] = {0};
    int left = 0, right = 0;
    int formed = 0;
    
    int ansLen = INT_MAX, ansLeft = 0, ansRight = 0;
    
    while (right < sLen) {
        char character = s[right];
        windowCounts[(int)character]++;
        
        if (tCount[(int)character] > 0 && windowCounts[(int)character] == tCount[(int)character]) {
            formed++;
        }
        
        while (left <= right && formed == uniqueChars) {
            character = s[left];
            
            if (right - left + 1 < ansLen) {
                ansLen = right - left + 1;
                ansLeft = left;
                ansRight = right;
            }
            
            windowCounts[(int)character]--;
            if (tCount[(int)character] > 0 && windowCounts[(int)character] < tCount[(int)character]) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    if (ansLen == INT_MAX) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    char* result = malloc(ansLen + 1);
    strncpy(result, s + ansLeft, ansLen);
    result[ansLen] = '\0';
    return result;
}

int main() {
    char s[1000], t[1000];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    char* result = solution(s, t);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

Each character in s is visited at most twice (once by right, once by left pointer)

✓ Linear Growth

Space Complexity

O(m + n)

Hash maps store character frequencies for strings s and t

⚡ Linearithmic Space

336.8K Views

Very High Frequency

~25 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler