Máximos 1s Consecutivos y Subcadenas sin Repeticiones

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