Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Clase 25 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

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

Nicolas Alpargatero

student•

Embarrada que la solución del ejercicio 3 no esté, me hubiera gustado ver como la profe manejaba esa k.

Christopher Andrés Guano Valencia

student•

👨‍💻 Soluciones en JavaScript / TypeScript

Comparto mis soluciones: .

Máxima Cantidad de 1s Consecutivos
Subcadena más larga sin caracteres repetidos
Subcadena más larga (reemplazo de k caracteres)
Encontrar todos los anagramas de una cadena

Héctor Hugo Cuzco Alvarez

student•

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

Héctor Hugo Cuzco Alvarez

student•

Posible solución para el problema número 3:

def characterReplacement(s: str, k: int) -> int:
    c_frequency = [0]*26
    longest_str_len =0
    l = 0
    for r in range(len(s)):
        indexR = indexOf(s[r])
        c_frequency[indexR] += 1
        cells_count = r - l + 1
        if cells_count - max(c_frequency) <= k:
            longest_str_len = max(longest_str_len, cells_count)
        else:
            indexL = indexOf(s[l])
            c_frequency[indexL] -= 1
            l += 1
    return longest_str_len

def indexOf(letter: str) -> int:
    return ord(letter) - ord("A")

Yader Velasquez

student•

Solución en go para max consecutive ones

/*
	- Have two pointers start, end = 0
	- Move end to the right
	- Count the amount of 1 (ones)
	- Calc the max length (start - end + 1)
	- Calc the amount of flipped values (length - ones)
	- When the amount of fillped values > k (it means we have flipped k times some 0s)
	start a new loop that move the start pointer foward
	- If the new start value is 1, decrease number of 1s.
	- The inner loop ends, when we are able to flip 0 again; (length - ones > k); then continue with the
	max length calc and moving the right pointer
*/

func maxOneConsecutive(nums []int, k int) int {
	var start, end, max, ones int

	for end <= len(nums)-1 {
		if nums[end] == 1 {
			ones++
		}

		// length - ones = number of flipped 0
		// we continue with the calc until we find a range where
		// we are allow to flip again
		for (end-start+1)-ones > k {
			// We are going to move the left pointer to calc
			// new possible consecutives 1, so we found a one
			// we remove it from the ones liest
			if nums[start] == 1 {
				ones--
			}
			// move the left pointer
			start++
		}
		max = int(math.Max(float64(max), float64(end-start+1)))
		end++
	}
	return max
}

José Ramón García

student•

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

def longitud_max_subcadena(s, k):
    frec = {} 
    p1 = 0
    max_frec = 0  
    max_long = 0  
    for p2 in range(len(s)):

        frec[s[p2]] = frec.get(s[p2], 0) + 1
        max_frec = max(max_frec, frec[s[p2]]) 

        if (p2 - p1 + 1) - max_frec > k:
            frec[s[p1]] -= 1
            p1 += 1

        max_long = max(max_long, p2 - p1 + 1)

    return max_long

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

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

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

def characterReplacement(s: str, k: int) -> int:
    c_frequency = [0]*26
    longest_str_len =0
    l = 0
    for r in range(len(s)):
        indexR = indexOf(s[r])
        c_frequency[indexR] += 1
        cells_count = r - l + 1
        if cells_count - max(c_frequency) <= k:
            longest_str_len = max(longest_str_len, cells_count)
        else:
            indexL = indexOf(s[l])
            c_frequency[indexL] -= 1
            l += 1
    return longest_str_len

def indexOf(letter: str) -> int:
    return ord(letter) - ord("A")

/*
	- Have two pointers start, end = 0
	- Move end to the right
	- Count the amount of 1 (ones)
	- Calc the max length (start - end + 1)
	- Calc the amount of flipped values (length - ones)
	- When the amount of fillped values > k (it means we have flipped k times some 0s)
	start a new loop that move the start pointer foward
	- If the new start value is 1, decrease number of 1s.
	- The inner loop ends, when we are able to flip 0 again; (length - ones > k); then continue with the
	max length calc and moving the right pointer
*/

func maxOneConsecutive(nums []int, k int) int {
	var start, end, max, ones int

	for end <= len(nums)-1 {
		if nums[end] == 1 {
			ones++
		}

		// length - ones = number of flipped 0
		// we continue with the calc until we find a range where
		// we are allow to flip again
		for (end-start+1)-ones > k {
			// We are going to move the left pointer to calc
			// new possible consecutives 1, so we found a one
			// we remove it from the ones liest
			if nums[start] == 1 {
				ones--
			}
			// move the left pointer
			start++
		}
		max = int(math.Max(float64(max), float64(end-start+1)))
		end++
	}
	return max
}

def longitud_max_subcadena(s, k):
    frec = {} 
    p1 = 0
    max_frec = 0  
    max_long = 0  
    for p2 in range(len(s)):

        frec[s[p2]] = frec.get(s[p2], 0) + 1
        max_frec = max(max_frec, frec[s[p2]]) 

        if (p2 - p1 + 1) - max_frec > k:
            frec[s[p1]] -= 1
            p1 += 1

        max_long = max(max_long, p2 - p1 + 1)

    return max_long

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 de Lista

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

Combinar Listas Ordenadas en un Array Ascendente

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 caracteres repetidos: patrón ventana deslizante

Algoritmo de Ventana Deslizante para Subcadenas Únicas

Playground: Longest Substring Without Repeating Characters

Algoritmo Python para Substring más Largo Sin Repeticiones

Retos de Algoritmos: Dos Apuntadores y Subcadenas

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Búsqueda Binaria

Algoritmo de búsqueda binaria en listas ordenadas

Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada

Búsqueda Binaria en Arreglos Rotados

Playground: Search in Rotated Arrays

Búsqueda en Arrays Rotados con C++

Búsqueda eficiente en matriz ordenada MxN

Búsqueda Binaria en Matrices 2D Ordenadas

Playground: Search 2D Array Matrix

Búsqueda Binaria en Matrices con Python

Próximos pasos

Estructuras de Datos Lineales: Conceptos y Aplicaciones