Sliding Window

51. Minimum Window Substring

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.

Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Constraints

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Follow-up

Could you find an algorithm that runs in O(m + n) time?

Dadas dos cadenas s y t de longitudes m y n respectivamente, devuelve la subcadena de ventana minima de s tal que cada caracter en t (incluyendo duplicados) este incluido en la ventana. Si no existe tal subcadena, devuelve la cadena vacia "".

Los casos de prueba se generaran de modo que la respuesta sea unica.

Ejemplos

Ejemplo 1

Entrada: s = "ADOBECODEBANC", t = "ABC"
Salida: "BANC"
Explicacion: La subcadena de ventana minima "BANC" incluye 'A', 'B' y 'C' de la cadena t.

Ejemplo 2

Entrada: s = "a", t = "a"
Salida: "a"
Explicacion: La cadena completa s es la ventana minima.

Ejemplo 3

Entrada: s = "a", t = "aa"
Salida: ""
Explicacion: Ambas 'a' de t deben estar incluidas en la ventana. Como la ventana mas grande de s solo tiene una 'a', se devuelve una cadena vacia.

Restricciones

m == s.length
n == t.length
1 <= m, n <= 10^5
s y t consisten en letras mayusculas y minusculas del ingles.

Desafio adicional

Podrias encontrar un algoritmo que se ejecute en tiempo O(m + n)?

minimum_window_substring.py

# Minimum Window Substring
# Find the smallest substring of s that contains all characters of t (including duplicates).
# Uses sliding window technique with two pointers.

from collections import Counter

s = "ADOBECODEBANC"
t = "ABC"

# Count how many of each character we need from t
need = Counter(t)
# How many unique characters we still need to satisfy
remaining = len(need)

left = 0
result = ""
result_len = float("inf")

# Track how many of each character we have in our current window
window = {}

for right in range(len(s)):
    char = s[right]
    window[char] = window.get(char, 0) + 1

    # If this character now meets the required count, one less to satisfy
    if char in need and window[char] == need[char]:
        remaining -= 1

    # When all characters are satisfied, shrink from the left
    while remaining == 0:
        # Update result if this window is smaller
        window_len = right - left + 1
        if window_len < result_len:
            result_len = window_len
            result = s[left:right + 1]

        # Remove left character from window and move left pointer
        left_char = s[left]
        window[left_char] -= 1
        if left_char in need and window[left_char] < need[left_char]:
            remaining += 1
        left += 1

print(result)  # BANC

Keyboard shortcuts

← h Previous problem

→ l Next problem

Esc Back to index

? Toggle this help