Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

Espero que hayas solucionado o al menos hayas intentado solucionar los retos de la clase anterior. De ser así, aquí te comparto la manera en que los solucioné. Recuerda que hay muchas formas de resolver un mismo problema, cuéntame qué te parecen estas soluciones, también revisa y aporta a las soluciones de otros Platzinautas. 👨‍🚀💚

1. Máxima Cantidad de 1s Consecutivos

Dado un arreglo de valores binarios y un entero k, encuentra el máximo número de 1s consecutivos. Puedes cambiar k 0s por el valor 1.

Ejemplo 1:

# Entrada: 
	nums = [1,1,1,0,0,0,1,1,1,0], k = 2
# Salida: 
	6

Explicación: [1,1,1,0,0,++1,1,1,1,1,1++] Los números en negrita se han pasado de 0 a 1. La submatriz más larga está subrayada.

Ejemplo 2:

# Entrada:
	nums = [0,0,1,1,0,0,1,1,0,1,1,0,0,1,1,1], k = 3
# Salida:
	10

Explicación: [0,0,++1,1,1,1,1,1,1,1,1,1++,0,0,0,1,1,1,1] Los números en negrita fueron volteados de 0 a 1. El sub-arreglo más largo está subrayado.

Solución:

def subarray_mas_larga(self, A: List[int], K: int) -> int:
   comienzo = 0
   cuentaCeros = 0
   mayorLongitud = 0
   for final in range(len(A)):
       if A[final] == 0: cuentaCeros += 1
       while cuentaCeros > K:
           if A[comienzo] == 0: cuentaCeros -= 1
           comienzo += 1
       mayorLongitud = max(mayorLongitud, final - comienzo + 1)
   return mayorLongitud

2. Subcadena más larga sin caracteres repetidos

Dada una cadena de caracteres, encuentra la longitud de la subcadena más larga sin repetir caracteres.

Ejemplo 1:

# Entrada:
	s = "abcabcbb"
# Salida:
	3

Explicación: La respuesta es "abc", con la longitud de 3.

Ejemplo 2:

# Entrada:
	s = "bbbbb"
# Salida:
	1

Explicación: La respuesta es "b", con la longitud de 1.

Solución:

def substring_mas_larga(self, s: str) -> int:
   comienzo = 0
   charAPos = {}
   mayorLongitud = 0
   for final in range(len(s)):
       if s[final] in charAPos and charAPos[s[final]] >= comienzo:
           comienzo = charAPos[s[final]] + 1
       charAPos[s[final]] = final
       mayorLongitud = max(mayorLongitud,final-comienzo+1)
   return mayorLongitud

3. Subcadena más larga (reemplazo de k caracteres)

Dada una cadena s y un número entero k. Devuelve la longitud de la subcadena más larga que contenga la misma letra de forma consecutiva. Donde puedes cambiar k caracteres de la cadena por otro caracter.

Ejemplo 1:

# Entrada:
	s = "ABAB", k = 2
# Salida:
	4

Explicación: Sustituir las dos "A" por dos "B" o viceversa.

Ejemplo 2:

# Entrada:
	s = "AABABBA", k = 1
# Salida:
	4

Explicación: Se sustituye la 'A' del medio por la 'B' y se forma "AABBBBA". La subcadena "BBBB" tiene las letras repetidas más largas, que son 4.

Solución:

def substring_mas_larga(self, s: str, k: int) -> int:
   if k > len(s): return len(s)
   contador = [0]*26
   mayorLongitud = k
   masOcurrente = 0

4. Encontrar todos los anagramas de una cadena

Dadas dos cadenas s y p, devuelva un arreglo con todos los índices de inicio de los anagramas de p en s. Puede devolver la respuesta en cualquier orden.

Un anagrama es una palabra o frase que se forma reordenando las letras de otra palabra o frase, normalmente utilizando todas las letras originales exactamente una vez.

Ejemplo 1:

# Entrada:
	s = "cbaebabacd", p = "abc"
# Salida:
	[0,6]

Explicación: La subcadena con índice inicial = 0 es "cba", que es un anagrama de "abc". La subcadena con índice inicial = 6 es "bac", que es un anagrama de "abc".

Ejemplo 2:

# Entrada:
	s = "abab", p = "ab"
# Salida:
	[0,1,2]

Explicación: La subcadena con índice inicial = 0 es "ab", que es un anagrama de "ab". La subcadena con índice inicial = 1 es "ba", que es un anagrama de "ab". La subcadena con índice inicial = 2 es "ab", que es un anagrama de "ab".

Solución:

def findAnagrams(self, s: str, p: str) -> List[int]:
   contadorAnagrama = [0]*26
   contadorString = [0]*26
   for num in p:
       contadorAnagrama[ord(num)-ord('a')]+=1
   comienzo = 0
   posiciones = []
   for final in range(len(s)):
       contadorString[ord(s[final])-ord('a')]+=1
       if contadorString == contadorAnagrama:
           posiciones.append(comienzo)
       if len(p) <= final - comienzo+1:
           contadorString[ord(s[comienzo])-ord('a')]-=1
           comienzo+=1
   return posiciones

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de dos apuntadores en algoritmos

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena

Cómo fusionar dos arrays ordenados sin memoria extra

Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Playground: Merge Two Sorted Lists

Intercalación de Listas Ordenadas en Python

Resolver el problema "Container with Most Water" en Python

Cálculo Óptimo de Área en Listas de Alturas

Playground: Container with Most Water

Implementación de solución de cálculo de área máxima en Java

Implementación de Trapping Rainwater en Complejidad Lineal

Retos de Algoritmos con Apuntadores en Python

Patrones de Dos Apuntadores: Soluciones a Problemas Comunes en Python

Ventana Deslizante

Patrón Ventana Deslizante para Análisis de Datos Secuenciales

Subcadena más larga sin repetir caracteres

Algoritmo de Ventana Deslizante para Subcadenas Únicas

Playground: Longest Substring Without Repeating Characters

Sliding Window para substring sin repeticiones

Retos de Algoritmos: Dos Apuntadores y Subcadenas