76. Min Window Substring

Sliding Window Problems: Common Pattern

Once left_idx and right_idx satisfy some condition, compute window length right_idx + 1 - left_idx, and compare it with historical max or min window length, and update records.

Sometimes we also need to store window's starting index.

Then move left_idx to the right until condition is no longer met, or left_idx > right_idx.

Minimum Window Substring

Let's use problem 76 as a demonstration.

We're given two strings source_str and target_str (the problem uses s and t, but source_str and target_str are more readable).

We have to find the shortest substring in source_str that contains all characters in target_str, including duplicates.

If no such substring exists, return "".

Our Old Friend Hash Map 🔢

First, count occurrences of each character in target_str, since these are the characters we must fully cover, including duplicates.

Call this map tgt_chars_counts.

Also prepare two variables upfront:

1. min_len: the shortest window length found so far, initialized to len(source_str) + 1 to imply no valid substring found yet
2. min_left_idx: the left_idx of the shortest window found, initialized to -1

Like Insurance: Over-coverage Is Fine, But Not Under

I. right_idx Always Moves Right

Create an integer variable unique_tgt_chars_coverage to track how many unique characters in target_str the current window fully covers.

Each time we move right_idx to the right, let char = source_str[right_idx].

First check if char is a key in tgt_chars_counts.

Only if it is, char is something we need to cover.

If so, decrement tgt_chars_counts[char] by 1, symbolizing that we've bought one more unit of insurance for char.

The moment tgt_chars_counts[char] drops to 0, it means full coverage of char has been achieved,

so increment unique_tgt_chars_coverage at that point.

One key point: even after char is fully covered,

every future occurrence of char should still decrement tgt_chars_counts[char].

Going negative is fine, as it just means over-coverage, which is allowed.

Just don't increment unique_tgt_chars_coverage more than once.

Only when tgt_chars_counts[char] drops to exactly 0 should our coverage count increase.

II. When Can left_idx Move Right?

Once unique_tgt_chars_coverage matches len(tgt_chars_counts), our current window fully covers all characters in target_str.

Quickly compute current window length: window_len = right_idx + 1 - left_idx.

Compare with min_len. If it's a new record,

also update min_window_left_idx with left_idx, since we'll eventually need it to slice source_str for the answer.

After recording and updating, move left_idx to the right.

A character falls out of window — let's call it removed_char = source_str[left_idx].

Again, check if removed_char is a key in tgt_chars_counts.

Only if it is, removed_char is something we were covering.

If so, increment tgt_chars_counts[removed_char] by 1, symbolizing that we've canceled one unit of insurance for removed_char.

The moment tgt_chars_counts[removed_char] gets greater than 0, removed_char, which was fully covered, is now exposed.

At that point, decrement unique_tgt_chars_coverage by 1.

Just like before, even if removed_char is already exposed,

each additional loss of removed_char should still increment tgt_chars_counts[removed_char],

since it means gap is growing and will need to be filled later.

Just don't decrement unique_tgt_chars_coverage more than once.

Only when it goes from 0 to positive should our coverage count decrease.

After a full scan, check if min_len equals len(source_str) + 1.

If so, no valid substring was found. Return "".

Otherwise, return source_str[min_window_left_idx: min_window_left_idx + min_len].

C++

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

string findMinWindowSubstring(string sourceString, string targetString) // LeetCode Q.76.
{
    unordered_map<char, int> tgtCharsCounts;

    for (const auto& character : targetString)
        tgtCharsCounts[character]++;

    int uniqueTgtCharsCount = tgtCharsCounts.size();

    // Must not exceed unique target chars count during sliding window.
    int uniqueTgtCharsCoverage = 0;

    int minWindowLeftIdx = -1;
    int minLen = sourceString.size() + 1; // Source length + 1: symbol of not found yet.

    int leftIdx = 0;
    for (int rightIdx = 0; rightIdx < sourceString.size(); rightIdx++) {
        char character = sourceString[rightIdx];
        if (tgtCharsCounts.find(character) != tgtCharsCounts.end()) {
            tgtCharsCounts[character]--;

            if (tgtCharsCounts[character] == 0) // Becomes covered.
                uniqueTgtCharsCoverage++;
        }

        while (uniqueTgtCharsCoverage == uniqueTgtCharsCount) // Can shrink window.
        {
            int windowLen = rightIdx + 1 - leftIdx;

            if (windowLen < minLen)
                minLen = windowLen, minWindowLeftIdx = leftIdx;

            char removedChar = sourceString[leftIdx];
            if (tgtCharsCounts.find(removedChar) != tgtCharsCounts.end()) {
                tgtCharsCounts[removedChar]++;

                if (tgtCharsCounts[removedChar] > 0) // Becomes uncovered.
                    uniqueTgtCharsCoverage--;
            }

            leftIdx += 1;
        }
    }

    if (minLen == sourceString.size() + 1)
        return "";

    return sourceString.substr(minWindowLeftIdx, minLen);
}

Python

def find_min_window_substring(source_str: str, target_str: str) -> str:  # LeetCode Q.76.
    tgt_chars_counts: dict[str, int] = dict()

    for char in target_str:
        if char not in tgt_chars_counts.keys():
            tgt_chars_counts.update({char: 0})
        tgt_chars_counts[char] += 1

    unique_tgt_chars_count = len(tgt_chars_counts)

    # Must not exceed unique target chars count during sliding window.
    unique_tgt_chars_coverage = 0

    min_window_left_idx = -1
    min_len = len(source_str) + 1  # Source length + 1: symbol of not found yet.

    left_idx = 0
    for right_idx, char in enumerate(source_str):
        if char in tgt_chars_counts.keys():
            tgt_chars_counts[char] -= 1

            if tgt_chars_counts[char] == 0:  # Becomes covered.
                unique_tgt_chars_coverage += 1

        while unique_tgt_chars_coverage == unique_tgt_chars_count:  # Can shrink window.
            window_len = right_idx + 1 - left_idx

            if window_len < min_len:
                min_len = window_len
                min_window_left_idx = left_idx

            removed_char = source_str[left_idx]
            if removed_char in tgt_chars_counts.keys():
                tgt_chars_counts[removed_char] += 1

                if tgt_chars_counts[removed_char] > 0:  # Becomes uncovered.
                    unique_tgt_chars_coverage -= 1

            left_idx += 1

    if min_len == len(source_str) + 1: return ""

    return source_str[min_window_left_idx: min_window_left_idx + min_len]

Time complexity: $O(|\text{source\_str}| + |\text{target\_str}|)$

Space complexity: $O(|\text{target\_str}|)$