Ventana deslizante para subcadenas
Implemente la ventana deslizante de tamaño variable para encontrar la subcadena más larga sin caracteres repetidos y la ventana mínima que contenga todos los caracteres objetivo.
Ventana deslizante para subcadenas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El concepto de ventana deslizante
Una ventana deslizante mantiene un subarray (o subcadena) entre un puntero izquierdo y uno derecho. En lugar de recalcular desde cero las propiedades de cada subarray posible en O(n²), la ventana se expande hacia la derecha al añadir un elemento y se contrae desde la izquierda al eliminarlo, manteniendo un estado acumulado en O(1) por paso. El resultado es un algoritmo O(n). La ventana se denomina «deslizante» porque avanza por el array sin retroceder.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Tamaño de ventana fijo frente a variable
Hay dos variantes de la ventana deslizante. En una ventana de tamaño fijo, ambos punteros avanzan al mismo ritmo y la ventana siempre contiene exactamente k elementos. En una ventana de tamaño variable, el puntero derecho se expande de forma voraz y el izquierdo solo se contrae cuando la ventana infringe una restricción. Las ventanas de tamaño variable resuelven problemas como «la subcadena más larga sin caracteres repetidos», donde el tamaño óptimo de la ventana no se conoce de antemano.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Subcadena más larga sin repeticiones
Este es el problema más conocido de ventana deslizante variable. Use un conjunto para realizar un seguimiento de los caracteres de la ventana actual. Expanda la ventana hacia la derecha; cuando encuentre un duplicado, redúzcala desde la izquierda hasta eliminarlo. Una versión más rápida usa un mapa hash que almacena el índice más reciente de cada carácter, lo que permite que el puntero izquierdo salte más allá del duplicado en un solo paso en lugar de avanzar poco a poco.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Subcadena de ventana mínima
Dadas las strings s y t, encuentre la ventana más pequeña de s que contenga todos los caracteres de t. Use dos mapas de frecuencias: need (caracteres requeridos) y have (caracteres de la ventana actual que cumplen el requisito). Lleve la cuenta de cuántos caracteres únicos de t se han satisfecho (contador formed). Expanda la ventana hacia la derecha para incluir caracteres; cuando se haya cubierto todo t, redúzcala desde la izquierda para minimizarla. Tiempo O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Plantilla de ventana deslizante
La mayoría de los problemas de ventana deslizante variable comparten una plantilla: expanda la ventana hacia la derecha para incluir el nuevo carácter, actualice el estado de la ventana, compruebe su validez y, si no es válida, redúzcala desde la izquierda hasta que vuelva a ser válida. La idea clave es que el puntero izquierdo solo avanza: nunca retrocede; por eso, el trabajo total de todos los pasos de reducción es O(n). La ventana visita cada elemento como máximo dos veces: una al añadirlo y otra al eliminarlo.
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutación en una string
Compruebe si alguna permutación del patrón p aparece como subcadena de s. Comprobar una permutación equivale a comprobar si una ventana tiene la misma frecuencia de caracteres que p. Mantenga una ventana deslizante de exactamente len(p) caracteres y compare los recuentos de frecuencias. Comparar objetos Counter completos en cada paso cuesta O(26) (constante para el inglés en minúsculas), por lo que el coste total es O(n × 26) = O(n).
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalseSubcadenas anagramas: contar todas
Encuentre todos los índices iniciales de los anagramas de p en s. Esta es la misma técnica de ventana fija que se usa para permutación en una string, pero en lugar de devolver True en la primera coincidencia, recopilamos todas las posiciones coincidentes. El tamaño de la ventana es fijo, len(p); la desplazamos por s y comparamos los recuentos de frecuencias en cada paso.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Subcadena más larga con como máximo 2 caracteres distintos
Una variante de la ventana deslizante: encuentre la subcadena más larga que contenga como máximo 2 caracteres distintos. Mantenga un mapa de frecuencias de los caracteres de la ventana actual. Cuando el mapa supere las 2 entradas, mueva el puntero izquierdo hacia la derecha (reduzca la frecuencia y elimine el carácter si llega a cero) hasta restablecer la restricción. Este es un caso particular del problema «como máximo k caracteres distintos», con k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Máximo de una ventana deslizante
Encuentre el máximo de cada ventana de tamaño k. Comprobar por fuerza bruta el máximo de cada ventana cuesta O(n×k). El enfoque óptimo usa una cola monotónica de índices: mantenga una cola decreciente para que el primero sea siempre el índice del máximo de la ventana actual. Elimine los índices del principio cuando salgan de la ventana y elimine los índices del final cuando entre un elemento mayor. El tiempo total es O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Cuándo usar la ventana deslizante
Recurra a la ventana deslizante cuando encuentre:
- Una subcadena o subarray con una restricción (longitud máxima, suma = k, como máximo k caracteres distintos)
- Un tamaño de ventana fijo con una agregación (máximo, suma, frecuencia)
- Preguntas sobre rangos contiguos (no sobre subconjuntos arbitrarios)
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Contar ventanas válidas: como máximo K
Algunos problemas piden contar los subarrays que cumplen una condición. Un truco útil es contar los subarrays con como máximo k caracteres distintos y después restar para obtener exactamente k: exactly(k) = at_most(k) - at_most(k-1). Cada llamada a at_most cuesta O(n), por lo que el coste total es O(n). La función at_most cuenta las ventanas en las que el número de caracteres distintos no supera k sumando right - left + 1 (todos los extremos izquierdos válidos para cada extremo derecho).
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: la ventana deslizante elimina el coste O(n²) al mantener un estado acumulado de la ventana que se actualiza en O(1) cuando los elementos entran y salen, las ventanas de tamaño fijo avanzan ambos punteros al mismo ritmo; las ventanas de tamaño variable expanden el puntero derecho de forma voraz y contraen el izquierdo solo cuando se infringe una restricción, y la subcadena de ventana mínima y la permutación en una string usan un estado de ventana basado en mapas de frecuencias, con un contador que registra cuántos caracteres requeridos están satisfechos en ese momento. A continuación exploraremos los anagramas y los mapas de frecuencias de caracteres.
Preguntas frecuentes
¿La lección «Ventana deslizante para subcadenas» es gratis?
Sí — el texto completo de «Ventana deslizante para subcadenas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Ventana deslizante para subcadenas»?
Implemente la ventana deslizante de tamaño variable para encontrar la subcadena más larga sin caracteres repetidos y la ventana mínima que contenga todos los caracteres objetivo. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Ventana deslizante para subcadenas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- API de strings de Python para entrevistas
- Ventana deslizante para subcadenas
- Anagramas y mapas de frecuencia de caracteres
- Codificación, inversión y palíndromos de strings