Home/Questions/Q 3537
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:53:53-05:00 In: ,

Minimum Window Substring: Why an integer frequency array beats HashMap in low-latency parsers

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

Most tutorials use two hash maps (dict or unordered_map) to track character counts and compare all keys on every step. Under high-throughput streaming text, hash lookups and memory allocations kill CPU cache performance. How can we implement this with a single 128-element integer vector and a single integer variable missing_count?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    Minimum Window Substring is the crown jewel of sliding window problems. The difference between a junior solution and a staff engineer solution comes down to how window validation is tracked.

    1. The Trap: Comparing Two Hash Maps

    In naive implementations, developers maintain two hash maps: target_counts and window_counts. Whenever the window slides, they loop through the keys of target_counts to see if the window is valid. That turns an $O(N)$ algorithm into $O(N cdot |Sigma|)$ with heavy hash table overhead!

    2. The Staff Engineer Pattern: Single Vector + Deficit Counter

    We can optimize this down to bare metal with two simple tricks:

    1. Fixed 128-integer Array: Standard ASCII fits inside 128 indices. An array of 128 integers takes 512 bytes, fitting completely inside an L1 data cache line.
    2. A Single Deficit Counter (required): We set required = len(t). When expanding the window with pointer r, if counts[s[r]] > 0, that character was actively needed, so we decrement required--. When required == 0, the window is 100% valid! We don’t have to check any other variables!

    Clean Python 3.12 Implementation

    def min_window(s: str, t: str) -> str:
    """Finds minimum window substring in strict O(|s| + |t|) time and O(1) space."""
    if not s or not t or len(s) < len(t):
        return ""

    # Frequency map using fixed 128 ASCII array
    freq = [0] * 128
    for char in t:
        freq[ord(char)] += 1

    required = len(t)
    min_len = float('inf')
    start_idx = 0
    left = 0

    for right in range(len(s)):
        r_char = ord(s[right])
        
        # If this character was still needed by t
        if freq[r_char] > 0:
            required -= 1
            
        freq[r_char] -= 1

        # While window satisfies all characters in t -> contract left boundary
        while required == 0:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start_idx = left

            l_char = ord(s[left])
            freq[l_char] += 1
            
            # If removing this character breaks the required quota
            if freq[l_char] > 0:
                required += 1
                
            left += 1

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

    Complexity Breakdown

    • Time Complexity: O(|s| + |t|). The right pointer advances |s| times. The left pointer advances at most |s| times. Total pointer advances = 2|s|.
    • Space Complexity: O(1) auxiliary space. Exactly 128 integers on the stack.
    • 0
  2. Anonymous
    Begginer

    Here is the C++20 Minimum Window Substring using a stack-allocated 128-element integer array and std::string_view to avoid memory allocations.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <string>
#include <string_view>
#include <array>

std::string_view minWindow(std::string_view s, std::string_view t) {
    if (s.empty() || t.empty() || s.size() < t.size()) return "";

    std::array<int, 128> freq{};
    for (char c : t) freq[static_cast<uint8_t>(c)]++;

    int required = static_cast<int>(t.size());
    int min_len = 1e9;
    int start_idx = 0;
    int left = 0;

    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        uint8_t r_char = static_cast<uint8_t>(s[right]);
        if (freq[r_char] > 0) required--;
        freq[r_char]--;

        while (required == 0) {
            int window_len = right - left + 1;
            if (window_len < min_len) {
                min_len = window_len;
                start_idx = left;
            }

            uint8_t l_char = static_cast<uint8_t>(s[left]);
            freq[l_char]++;
            if (freq[l_char] > 0) required++;
            left++;
        }
    }
    return min_len == 1e9 ? "" : s.substr(start_idx, min_len);
}

int main() {
    std::string s = "ADOBECODEBANC";
    std::string t = "ABC";
    std::cout << "Minimum Window Substring: " << minWindow(s, t) << "n"; // Expected: "BANC"
    return 0;
}

    Zero Allocations: std::string_view creates no heap strings; the array fits into CPU L1 cache.

    • 0