Retos de Algoritmos: Dos Apuntadores y Subcadenas

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

Al igual que en el módulo anterior de dos apuntadores, ahora vamos a poner en práctica todo lo que hemos aprendido durante este módulo con algunos retos. ¡Empecemos! Espero tus soluciones en los aportes. 😄

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.

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.

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.

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".

Christopher Andrés Guano Valencia

student•

Ejercicios de Ventana deslizante

👨‍💻 Comparto la explicación de cada ejercicio (en inglés). También coloco el nombre y código de cómo aparece en Leetcode (no me deja colocar el enlace 😛), es útil escribir el código ahí porque tiene varios tests para cada ejercicio. .

Máxima Cantidad de 1s Consecutivos - 485. Max Consecutive Ones
Subcadena más larga sin caracteres repetidos - 3. Longest Substring Without Repeating Characters
Subcadena más larga (reemplazo de k caracteres) - 424. Longest Repeating Character Replacement
Encontrar todos los anagramas de una cadena - 438. Find All Anagrams in a String

Carlos Raúl Romero Martínez

student•

Que agradeble sujeto, me resulto muy util tu aporte , gracias a esto puedo probas mis soluciones

Iván Alexander Luce Villegas

student•

💚Gracias por el aporte, el primer problema no es el 485 en leetcode, ese es ligeramente diferente y se resuelve con un simple contador, este es el problema real: 1. Máxima Cantidad de 1s Consecutivos - 1004. Max Consecutive Ones III

Luis Rodolfo Altuve Cáceres

student•

En el problema 1, lo que indica el ejemplo 1 (el tamaño de la lista) no concuerda con la explicación.

Algo similar ocurre en el ejemplo 2 del mismo problema. Y por lo que indica, es reemplazar los valores, no agregarlos.

Pro Code

student•

Coincido contigo en que el ejemplo y la explicación no concuerdan, sin embargo eso de reemplazarlos y no agregarlos debe ser solo para la explicación, porque:

En el ejemplo 1: nums = [1,1,1,0,0,0,1,1,1,0], k = 2 Incluso la salida con la solución que está en la siguiente sección(25 Soluciones), da como resultado 5, por ejemplo [1,1,1,0,0,1,1,1,1,1] puesto que solo se pueden reemplazar dos 0 por 1. En la explicación Explicación: [1,1,1,0,0,1,1,1,1,1,1] le ha aumentado un 1 demás.

En el ejemplo 2: nums = [0,0,1,1,0,0,1,1,0,1,1,0,0,1,1,1], k = 3 Con la solución también de la siguiente sección, la salida si es 10, solo que en la explicación no concuerdan las posiciones de los 1 y 0 como estaban originalmente, [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1], como deben ser concurrentes y solo se pueden reemplazar tres 0 por 1, la representación a la respuesta sería [0,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1].

Carlos Castro

student•

Este sistema de comentario es tan cerrado. ¿Por qué no puedo poner el link al ejercicio de leetcode? cuando es claro que es un copy-pase traducido de ese portal.

Cada vez me doy cuenta de lo pobre que hace Platzi las cosas. El objetivo es aprender y aquí hay muchas cosas que bloquean el aprendizaje.

¿Que no se fijaron que cuando dice "los números en negrita" se están refiriendo a la explicación? Nada de ese texto está en negrita, siendo que en leetcode si se aprecia bien ...

Posiblemente hasta este mensaje sea baneado...

Carlos Castro

student•

El link al problema 1 se llama "1004. Max Consecutive Ones III".

Andres Silva Vega

student•

Son ejercicios tradicionales de programación que no solamente están en leetcode. Al margen de que sean o no un copy paste de otro lugar lo importante es entender y aplicar el concepto, como si fuera una receta de cocina; no vas a pedirle a tu maestro chef que te enseñe cocina con solo recetas originales de él. En mi caso encontré mejores explicaciones a varios de estos algoritmos en youtube, nuestra joven y bella profe no tiene mucho don de palabra

Andres Silva Vega

student•

Este algoritmo resuelve los ejercicios 1 y 3; hay que pasarle siempre strings

const cadenaMasLargaConReemplazo = (s, k) => {
    let max = 0;
    let iz = 0;
    let der = 0;
    let letraAlto = 0;
    let subSirve = [];
    let boxLetras = new Map();
    var count = 0;
    boxLetras.set(s[der],1);
    while(der < s.length){
        count++;
        letraAlto = 0;
        boxLetras.forEach(( value, ele) => letraAlto = value > letraAlto ? value : letraAlto );
        let subLong = der - iz + 1;
        if((subLong - letraAlto) <= k){
            if(subLong > max){
                subSirve = [iz, der];
                max = subLong;
            }
            der++;
            if(boxLetras.has(s[der])){
                boxLetras.set(s[der],boxLetras.get(s[der])+1);
            } else {
                boxLetras.set(s[der], 1);
            }
        } else {
            boxLetras.set(s[iz],boxLetras.get(s[iz])-1);
            iz++;
        }
    }
    console.log(`Bucleado: ${count} string: ${s.length}, recorrido el string ${count/s.length}`);
    return [max, s.substring(subSirve[0],subSirve[1]+1)];
}
```![](https://static.platzi.com/media/user_upload/upload-d74f0aba-9c0a-47a1-bca0-0bd7092b5bbf.png)

Kengya Moncada

student•

function ventanaDeslizante(){
  let split = s.split("");
  let left = 0;
  let right = 0;
  let longSTR = 0;
  const hashMap = new Set();

  for(let right = 0; right < split.length;right++){
    let letter = split[right];
    if(!hashMap.has(letter)){
      hashMap.add(letter);
      longSTR = Math.max(longSTR, hashMap.size);
      right++
    }else{
      hashMap.delete(s[left]);
      left++
    }
  }
  return longSTR
}

Kengya Moncada

student•

let s = [1,1,0,1,1,1];

function ventanaDeslizante(){
  let maxL = 0;
  let maxG = 0;

  for(let i = 0; i < s.length; i++ ){
    if(s[i] === 1){
      maxL++
      maxG = Math.max(maxL, maxG)
    }else{
      maxL = 0;
    }
  }
  return maxG;
}
ventanaDeslizante();

Nicolas Alpargatero

student•

Máxima Cantidad de 1s Consecutivos
Subcadena más larga sin caracteres repetidos
Subcadena más larga (reemplazo de k caracteres) : Mi solución solo funcionó para los ejemplos de la clase, cuando quise probar más se rompio 🫠, investigue, y era mi k me faltaba parte de lógica
Encontrar todos los anagramas de una cadena, mi solución solo daba parte de lo esperado, me toco con ayuda, me toca practicar más

Ivan Camilo Buitrago Buitrago

student•

en que programa lo estas realizando, donde haces las pruebas?

Nicolas Alpargatero

student•

Jupyter Nootebook

Luis Rodolfo Altuve Cáceres

student•

El ejemplo 2 es el mismo que explico la profesora? eso parece

Pro Code

student•

const cadenaMasLargaConReemplazo = (s, k) => {
    let max = 0;
    let iz = 0;
    let der = 0;
    let letraAlto = 0;
    let subSirve = [];
    let boxLetras = new Map();
    var count = 0;
    boxLetras.set(s[der],1);
    while(der < s.length){
        count++;
        letraAlto = 0;
        boxLetras.forEach(( value, ele) => letraAlto = value > letraAlto ? value : letraAlto );
        let subLong = der - iz + 1;
        if((subLong - letraAlto) <= k){
            if(subLong > max){
                subSirve = [iz, der];
                max = subLong;
            }
            der++;
            if(boxLetras.has(s[der])){
                boxLetras.set(s[der],boxLetras.get(s[der])+1);
            } else {
                boxLetras.set(s[der], 1);
            }
        } else {
            boxLetras.set(s[iz],boxLetras.get(s[iz])-1);
            iz++;
        }
    }
    console.log(`Bucleado: ${count} string: ${s.length}, recorrido el string ${count/s.length}`);
    return [max, s.substring(subSirve[0],subSirve[1]+1)];
}
```![](https://static.platzi.com/media/user_upload/upload-d74f0aba-9c0a-47a1-bca0-0bd7092b5bbf.png)

function ventanaDeslizante(){
  let split = s.split("");
  let left = 0;
  let right = 0;
  let longSTR = 0;
  const hashMap = new Set();

  for(let right = 0; right < split.length;right++){
    let letter = split[right];
    if(!hashMap.has(letter)){
      hashMap.add(letter);
      longSTR = Math.max(longSTR, hashMap.size);
      right++
    }else{
      hashMap.delete(s[left]);
      left++
    }
  }
  return longSTR
}

let s = [1,1,0,1,1,1];

function ventanaDeslizante(){
  let maxL = 0;
  let maxG = 0;

  for(let i = 0; i < s.length; i++ ){
    if(s[i] === 1){
      maxL++
      maxG = Math.max(maxL, maxG)
    }else{
      maxL = 0;
    }
  }
  return maxG;
}
ventanaDeslizante();

Retos de Algoritmos: Dos Apuntadores y Subcadenas

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