Algoritmo Python para Substring más Largo Sin Repeticiones

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

Resumen

¿Cómo podemos encontrar el Longest Substring Without Repeating Characters?

En este artículo, nos sumergimos en la implementación del algoritmo para encontrar el Longest Substring Without Repeating Characters utilizando Python. Este problema puede parecer complejo si se enfrenta de forma incorrecta, pero utilizando estructuras y tácticas adecuadas, podemos resolverlo de manera eficiente. ¡Vamos a descubrir cómo hacerlo!

¿Cómo iniciamos el desarrollo del algoritmo?

Comenzamos definiendo las variables necesarias para implementar nuestro algoritmo:

inicio: un apuntador inicializado en cero que ayudará a definir el comienzo de la ventana deslizante que revisaremos.
fin: otro apuntador que recorrerá el string, pero que no es necesario inicializar explícitamente al principio, ya que avanzará automáticamente con cada iteración.
caracteres_a_posicion: un diccionario que almacenará la posición más reciente de cada carácter en el string.
mayor_longitud: un entero que almacenará la longitud del substring más largo encontrado sin caracteres repetidos.

¿Cómo administramos la detección de duplicados?

Para detectar la repetición de caracteres, seguimos los pasos descritos a continuación:

Iteración del string: Recorremos cada carácter del string con el apuntador fin.
Revisión de duplicados: Si el carácter ya está en caracteres_a_posicion y su posición es mayor o igual al inicio actual, esto indica un duplicado y, por tanto, actualizamos el inicio al índice siguiente al de la última aparición del duplicado.
Actualización de la posición: Independientemente de que haya un duplicado o no, actualizamos la posición de cada carácter en caracteres_a_posicion.
Comparación de longitud: Calculamos la longitud del substring actual (fin - inicio + 1) y la comparamos con mayor_longitud, actualizando este último si es necesario.

El código para este algoritmo en Python es el siguiente:

def longest_substring_without_repeating_characters(s):
    inicio = 0
    caracteres_a_posicion = {}
    mayor_longitud = 0
    
    for fin in range(len(s)):
        caracter_actual = s[fin]
        
        if caracter_actual in caracteres_a_posicion and inicio <= caracteres_a_posicion[caracter_actual]:
            inicio = caracteres_a_posicion[caracter_actual] + 1
        
        caracteres_a_posicion[caracter_actual] = fin
        mayor_longitud = max(mayor_longitud, fin - inicio + 1)
    
    return mayor_longitud

¿Qué complejidades nos encontramos en el algoritmo?

La eficiencia del algoritmo se ve reflejada en dos tipos de complejidades:

Complejidad temporal: Es O(n), donde n es el número de caracteres en el string. Esto se debe a que recorremos el string solo una vez y utilizamos operaciones de búsqueda y almacenamiento constantes.
Complejidad espacial: Es O(n) en el peor caso, ya que el diccionario caracteres_a_posicion puede llegar a almacenar todos los caracteres del string si todos son distintos.

Este desarrollo nos muestra cómo podemos enfrentar problemas de algoritmos en principio complejos, utilizando un enfoque sistemático y eficiente. Los invitamos a seguir aprendiendo y reforzando habilidades de programación para resolver desafíos de forma efectiva. ¡El aprendizaje nunca termina!

Juan David Gaviria Agudelo

student•

Creo que en esta clase hay un error en la linea 7, deberia de ser:

inicio = caracteristicaAposicion[s[fin]] + 1

De esta manera evitamos el error

Luis Rodolfo Altuve Cáceres

student•

creo que seria equivalente a:

inicio = fin + 1

probe con algunos casos y me dio Ok

Nicolas Alpargatero

student•

con el inicio = fin + 1 no toma no es suficiente, s = 'jdkafnlcdsalkxcmpoiuytfccv' -->14. cuando deberia ser 15

Irving Juárez

student•

Se me hace compleja la implementación y probablemente tenga bugs, ya que aunque se hizo una prueba de escritorio, esta se debió haber hecho para más de un ejercicio, ya que siempre puede haber edge cases que a primera vista no son muy fáciles de vislumbrar. . Aquí les dejo mi implementación (en python), me parece que es un poco más fácil de entender y fue testeado con varios edge cases, por lo que es un poco más resistente a algunos escenarios inusuales.

def get_longest_substring(s: str):
	size = len(s)
	if (size == 0):
		raise ValueError()

	p1 = 0
	p2 = 1
	longest_length = 1

	while p2 < size:
		substring = s[p1:p2]
		p2_value = s[p2]

		if p2_value in substring:
			longest_length = max(longest_length, len(substring))
			repeated_char_index = substring.index(p2_value) + 1
			p1 += repeated_char_index

		p2 += 1

	return longest_length

Julio Serratos

student•

De hecho la solucion de la profesora me parece bastabte elegante, pero creo que es cuestion de gustos

Irving Juárez

student•

El código es elegante, pero no habla por si mismo. Probablemente tengas que pasar un rato tratando de entender que hace cada parte del código. Esto pasa porque algún string no tiene un nombre adecuado o porque simplemente no tiene nombre. Eso ayuda bastante a que alguien más (o tu yo del futuro) entienda la implementación

Reinaldo Mendoza

student•

Que buena expicacion

Luis Antonio Ibarra Salgado

student•

Estaría bueno que al momento de explicar como va funcionando el código (que lo hace manual porque en algunas entrevistas así te lo piden) estaría más padre que usara la herramienta de debug de VS Code para ver como van cambiando los valores de las variables

Nicolas Alpargatero

student•

Comparto la solución de la profe reparando el bug (gracias copilot) no es inicio = s[fin] + 1 sino inicio = caracteresAposicion[s[fin]] + 1 también me había pasado este error 😅 como que se confunde uno con quien itera, pero de seguro si lo hubiera ejecutado se hubiera dado cuenta.

Victor Alfredo Matzar Say

student•

No entendí porque concateno el carácter en s[fin] + 1, para luego asignarlo al iterador inicio.

inicio = s[fin] + 1

Nicolas Alpargatero

student•

Por si alguien mas lee esto. Creo que fue solo error de elegir el string, también me paso, pero la solución al bug es esta: inicio = caracteresAposicion[s[fin]] + 1

Luis Sandoval

student•

Adjunto mi solución

    public static int LongestSubStringWithoutRepeat(string text)
    {
        var hash = new HashSet<char>();
        int count = 0;
        int max = 0;
        int p = 0;

        while (text.Length > p)
        {
            if (!hash.Contains(text[p]))
            {
                hash.Add(text[p]);
                count++;
                p++;
            }
            else
            {
                if (count > max) max = count;
                hash.Clear();
                count = 0;
            }
        }
        if (count > max) max = count;
        return max;
    }

Carlos Hernandez

student•

Mi solución en Javascript: const getLongestSubstringWithoutRepeatingCharacters = (completeString) => { const stringSize = completeString.length; let leftPointer = 0, rightPointer = 0; let substringMap = new Map(); let longestSubstring = 0; while (leftPointer < (stringSize - 1)) { const letterPosition = substringMap.get(completeString[rightPointer]); const substringLength = substringMap.size; if (letterPosition) { if (substringLength > longestSubstring) longestSubstring = substringLength; substringMap.clear(); leftPointer++; rightPointer = leftPointer; continue; } substringMap.set(completeString[rightPointer], rightPointer); rightPointer++; if (rightPointer > stringSize - 1) { if (substringLength > longestSubstring) longestSubstring = substringLength; break; } } return longestSubstring;} console.log(getLongestSubstringWithoutRepeatingCharacters('abcdefe')); //6console.log(getLongestSubstringWithoutRepeatingCharacters('abcabcbb')); //3console.log(getLongestSubstringWithoutRepeatingCharacters('abcdefdhijklmnopmoj')); //12

const getLongestSubstringWithoutRepeatingCharacters = (completeString) => {
    const stringSize = completeString.length;

    let leftPointer = 0, rightPointer = 0;
    let substringMap = new Map();
    let longestSubstring = 0;

    while (leftPointer < (stringSize - 1)) {
        const letterPosition  = substringMap.get(completeString[rightPointer]);
        const substringLength = substringMap.size;

        if (letterPosition) {
            if (substringLength > longestSubstring) longestSubstring = substringLength;
            substringMap.clear();
            leftPointer++;
            rightPointer = leftPointer;
            continue;
        }

        substringMap.set(completeString[rightPointer], rightPointer);
        rightPointer++;

        if (rightPointer > stringSize - 1) {
            if (substringLength > longestSubstring) longestSubstring = substringLength;
            break;
        }
    } 

    return longestSubstring;
}

console.log(getLongestSubstringWithoutRepeatingCharacters('abcdefe')); //6
console.log(getLongestSubstringWithoutRepeatingCharacters('abcabcbb')); //3
console.log(getLongestSubstringWithoutRepeatingCharacters('abcdefdhijklmnopmoj')); //12

Nicolas Lopez

student•

Mi codigo en Java mostrando el total de caracteres sin repetir, y la cadena mas larga.public class LongestSubstringWithoutRepeatingCharacters { public static void main(String[] args) { String s = "abcabcfbb"; int k = s.length(); System.out.println(longestSubstringWithOnlySet(s, k)); }

private static int longestSubstringWithOnlySet(String s, int k) { Set<Character> set = new HashSet<>(); int right, result = 0; char[] arr = s.toCharArray();

StringBuilder stringBuilder = new StringBuilder(); for (right = 0; right < k; right++) { if(!(set.add(arr[right]))){ for (int i = 0; i < set.size()-1; i++) { String str = set.toString(); stringBuilder = new StringBuilder(str); } if(set.size()>result){ result = set.size(); } set.clear(); right--; } } System.out.println("The longest substring is: " + stringBuilder); return result; } }

public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        String s = "abcabcfbb";
        int k = s.length();
        System.out.println(longestSubstringWithOnlySet(s, k));
    }

    private static int longestSubstringWithOnlySet(String s, int k) {
        Set<Character> set = new HashSet<>();
        int right, result = 0;
        char[] arr = s.toCharArray();

        StringBuilder stringBuilder = new StringBuilder();
        for (right = 0; right < k; right++) {
            if(!(set.add(arr[right]))){
                for (int i = 0; i < set.size()-1; i++) {
                    String str = set.toString();
                    stringBuilder = new StringBuilder(str);
                }
                if(set.size()>result){
                    result = set.size();
                }
                set.clear();
                right--;
            }
        }
        System.out.println("The longest substring is: " + stringBuilder);
        return result;
    }
}

Luis Alberto Ramírez Botero

student•

Les comparto una breve esplicaccion paso a paso:

caracteresAposicion = {}
s = "abcaibe"
inicio = 0
mayorLongitud = 0
for fin in range(len(s)):
    if s[fin] in caracteresAposicion and inicio <= caracteresAposicion[s[fin]]:
        print("Estamos en la condicion y se encontro: ", s[fin], " como letra repetida")
        print("Ahora esa letra: ", s[fin]," que tiene como valor en el diccionaro", caracteresAposicion[s[fin]], "va a tomar el valor de: ", fin)
        print("Y el valor de inicio es de ", caracteresAposicion[s[fin]])
        print("Valores que se encuentran en el diccionario al validar la condicion", caracteresAposicion)
        inicio = caracteresAposicion[s[fin]] + 1
        print("Este es el valor de Inicio al sumarle 1: ", inicio)
    caracteresAposicion[s[fin]] = fin
    print("Valores que se guardan en el diccionario antes y despues de pasar la condicion:", caracteresAposicion)
    mayorLongitud = max(mayorLongitud, fin - inicio + 1)
print("la cadena con mayor longitud es de: ", mayorLongitud)

Marcos Mesias

student•

Mejore el código. El codigo es brillante, espero algún dia tener la capacidad de hacer codigos a ese nivel. Pero el codigo no es perfecto, ya que usa la función "in" y "in" hace una busqueda, osea una iteracion, si una entrada tiene miles de caracteres, el codigo se volveria muy lento y la complejidad seria O(n**). Pero yo mejore el codigo, en vez de usar "in" yo hice uso de "get()" donde su tiempo es casi O(1), pero es mucho mejor que usar "in".

Ashley Andres Alejo Guilarte

student•

Mi codigo en Java:

yo utilizo p1 para la posicion inicial y p2 el que se va moviendo.

mientras que p2 sea menor al tamaño de la cadena se seguira iterando hasta evaluar la cadena completa. se pueden apreciar las letras en la linea 20 y la cadena en la linea 21, a medida que se forma la nueva cadena se incrementa el tamaño sin incrementar el valor maximo, hasta que se ve que a la 3era iteracion (Cuando la cadena es abc) se mantiene en 3 el valor longestLent, probe agregando mas letras (d,e,f,g) despues de las primeras 3 posisicon es y funciona.

Ivo Zayas

student•

comparto mi solución con JS:

function longestSubstring(s){
    let p1 = 0
        p2 = p1 + 1
        subString = s[p1]
        largestLength = 0

    while(p2 < s.length) {
        if(subString.includes(s[p2])){
            p1 = p2
            p2 = p1 + 1
            subString = s[p1]
        } else {
            subString = subString + s[p2]
            p2++

            if(subString.length > largestLength){
                largestLength = subString.length
            }
        }

    }

    return largestLength
}

Emilio Sala

student•

Posible solucion en python Creo que se podría mejorar si la ultima comparacion es igual a la anterior, entonces el p1 se podria actualizar a p2

def longest_substring(str):
   maxLength = 0
   if len(str) <= 1:
      return len(str)
   #recorremos con p1
   p1 = 0
   while (p1 < len(str)-1): 
      #p2 será el siguiente
      p2 = p1 + 1
      currentDict = {}
      #añadimos el primer elemento
      currentDict[str[p1]] = 1
      while p2 < len(str) and currentDict.get(str[p2]) == None:
         currentDict[str[p2]] = 1
         p2 += 1
      #print(currentDict)
      if p2 - p1 > maxLength:
         maxLength = p2 - p1
      p1 = p1 +1
   
   return maxLength

Martín Gutiérrez Hernández

student•

No etendia como funcionaba, pero despues de hacer varias pruebas de escritorio entendi que es lo que pensaba la maestra. Aqui esta el código en Rust

Victor Alfredo Matzar Say

student•

Mi solución :)

def lengthOfLongestSubstring(s):
   uniqueLetters = set()
   highestLen = 0
   pointer1 = 0
   pointer2 = 0
   
   while pointer2 < len(s):
       if s[pointer2] in uniqueLetters:
           highestLen = len(uniqueLetters) if highestLen < len(uniqueLetters) else highestLen
           if s[pointer1] == s[pointer2]:
               pointer1+=1 
               pointer2+=1 
           else:
               uniqueLetters.remove(s[pointer1])
               pointer1+=1
       else:
           uniqueLetters.add(s[pointer2])
           pointer2+=1
   return highestLen

Alvaro Diego Pérez Vázquez

student•

My solution with java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> hash = new HashSet(); //elegimos estructura con chars únicos
        int biggestLength = 0;
        int pointerL = 0, pointerR = 0; //2 pointers (patrón ventana deslizante)
        while(pointerR < s.length()){
            if( !hash.contains(s.charAt(pointerR)) ){//Si no existe, el char lo agrega al hash, el último pointer de la ventana lo incrementamos y actualizamos el valor max al momento
                hash.add(s.charAt(pointerR));
                pointerR++;
                biggestLength = Math.max(hash.size(),biggestLength);
            }else{// si existe, eliminamos el char repetido e incrementamos el primer pointer de la ventana
                hash.remove(s.charAt(pointerL));
                pointerL++;
                
            }
        }
        return biggestLength;//será la longitud mas grande registrada
    }
}

Christopher Andrés Guano Valencia

student•

👨‍💻 Solución en JavaScript / TypeScript

Utilicé un Set en lugar de un Map / diccionario. . Longest Substring Without Repeating Characters - 3 Leetcode

Ricardo Betancourt

student•

Mi solucion en JS

function lengthOfLongestSubstring(letras) {
    let maxSize = 0 ;
    let p1 = 0;
    let map = new Map();
    for(let p2 = 0; p2 < letras.length; p2++ ) {
        const actualindex = map.get(letras[p2])
        if(actualindex  == undefined || actualindex < p1) {
            map.set(letras[p2], p2)
            const newMaxSize = p2 - p1 +1;
            if(newMaxSize > maxSize){
                maxSize = newMaxSize;
            }
        } else {
                p1 = actualindex + 1
                map.set(letras[p2],p2)
        }
    }
    return maxSize;
}