Cursos Empresas Blog Live Conf Eventos Precios

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

Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Clase 21 de 29

Clase 21 / 29

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

Comentarios (6)6 comentarios

Nicolas Alpargatero

Hace 3 años

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

Hace 4 años

👨‍💻 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

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

Yader Velasquez

Solución en go para max consecutive ones

José Ramón García González

Hace 2 años

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Progreso del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos