Playground: Longest Substring Without Repeating Characters

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

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

Comentarios

Tomas Pucutay

student•

Que excelente, la primera formulación que realicé con set, no caí en la cuenta de que los 2 ciclos for que consideraba tenían complejidad temporal O(n2). Esta fue mi solución y corrió las pruebas.

def lengthOfLongestSubstring(s):
    p1 = p2 = 0
    res = []
    for p1 in range(len(s)):
        count = count_set = 0
        st = set()
        for p2 in range(p1,len(s)):
            st.add(s[p2])
            count_set = len(st)
            count += 1
            if count_set != count:
                break
        res.append(len(st))
    return max(res)

Le pedí a ChatGPT que me ayude a optimizar para poder lograr la complejidad temporal O(n) y me entregó esto, está excelente:

def lengthOfLongestSubstring(s):
    p1 = p2 = 0
    st = set()
    max_length = 0
    
    while p2 < len(s):
        if s[p2] not in st:
            st.add(s[p2])
            max_length = max(max_length, len(st))
            p2 += 1
        else:
            st.remove(s[p1])
            p1 += 1
    
    return max_length

Nicolas Alpargatero

student•

buena opción usar set en vez de dict.

Juan Pablo Reina Gutierrez

student•

Hola, cual es el test_surprise_string?

Nicolas Alpargatero

student•

me paso lo mismo, lo solucione cambiando a O(n) pero a otro compañero siendo O(n^2) si se lo tomo como valido.

Miguel Angel Reyes Moreno

student•

Estoy en la mismas, me falla solo ese caso

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

#include<iostream>
#include<string>
#include<unordered_map>

int longest_substring(const std::string &str){

	int longest = 0;
	int p1 = 0;
	int p2 = 0;
	std::unordered_map<char,int> imhere;

	while(p2 < str.size() &&  p1 < str.size()){

		imhere[str[p2]]++;
		if(imhere[str[p2]] == 1){
			p2++;
		}
		else{
			longest = longest > (p2 - p1) ? longest : (p2 - p1);
			imhere[str[p1]] = 0;
			p1++;
		}
	}

	return longest;
}


int main(){

	std::string input = "abcabcbb";
	std::cout << longest_substring(input) << std::endl;

	input = "jdkafnlcdsalkxcmpoiuytfccv";
	std::cout << longest_substring(input) << std::endl;

	return 0;
}

Jacquelinne Castro Martinez

student•

Mi código en Go:

package main

import (
	"fmt"
	"math"
)

func longestSubstring(s string) int {
	var result float64 = 0
	p1 := 0
	chars := make(map[rune]int)

	for p2, char := range s {
		// Si la
		if lastPosition, found := chars[char]; found && lastPosition >= p1 {
			p1 = lastPosition + 1
		}
		chars[char] = p2
		result = math.Max(float64(result), float64(p2-p1+1))
	}

	return int(result)
}

func main() {
	s1 := "abcabcbb"
	fmt.Println(longestSubstring(s1))

	s2 := "jdkafnlcdsalkxcmpoiuytfccv"
	fmt.Println(longestSubstring(s2))
}

John Eduard Meneses González

student•

This is my solution!!

def lengthOfLongestSubstring(s):
    char_index = {}  # Diccionario para almacenar la última posición de cada carácter
    left = 0  # Límite izquierdo de la ventana deslizante
    max_length = 0  # Longitud máxima de la subcadena sin repetir
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1  # Mueve el límite izquierdo para evitar repetidos
        
        char_index[s[right]] = right  # Actualiza la última posición del carácter
        max_length = max(max_length, right - left + 1)  # Calcula la longitud máxima
    
    return max_length

Bryan Castano

student•

Hola Chicos , \nYo dejo my Code Snippet aqui abajo, Yo me insppirado en alguna de sus respuestas previas . Espero les Sirva para crear foramas en O (n) \n

def lengthOfLongestSubstring(s):
   # Tu código aquí 👇....

   p1 = 0
   largestLen = 0

   chars = { }

   for p2 , char in enumerate( s ) : 

      if ( char in chars ) : 

         p1 = max( p1, chars[ char ] + 1 ) 

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

      chars[ char ] = p2 


   return largestLen


response = lengthOfLongestSubstring("abcabcbb")
print(response)

response2 = lengthOfLongestSubstring("jdkafnlcdsalkxcmpoiuytfccv")
print(response2)


```def lengthOfLongestSubstring(s):   # Tu código aquí 👇....
&#x20;  p1 = 0   largestLen = 0
&#x20;  chars = { }
&#x20;  for p2 , char in enumerate( s ) :&#x20;
&#x20;     if ( char in chars ) :&#x20;
&#x20;        p1 = max( p1, chars\[ char ] + 1 )&#x20;
&#x20;     largestLen = max( largestLen , ( p2-p1+1) )&#x20;
&#x20;     chars\[ char ] = p2&#x20;

&#x20;  return largestLen

response = lengthOfLongestSubstring("abcabcbb")print(response)
response2 = lengthOfLongestSubstring("jdkafnlcdsalkxcmpoiuytfccv")print(response2)

Cesar Augusto Mora Castilo

student•

# Tu código aquí 👇 p1 = 0 p2 = p1 + 1 current_string = set(s[p1]) max_len = 0 while p1 < p2 < len(s): if s[p2] in current_string: if len(current_string) > max_len: max_len = len(current_string) current_string.clear() p1 += 1 p2 = p1 + 1 current_string.add(s[p1]) else: current_string.add(s[p2]) p2 += 1 return max_len

response = lengthOfLongestSubstring("abcabcbb") print(response)

response2 = lengthOfLongestSubstring("jdkafnlcdsalkxcmpoiuytfccv") print(response2)

franklin yancoba

student•

Hola, mi solucion la realice con un map, usando solamente un apuntador creo que esta mal para fines del curso que es usar los dos apuntadores pero aun no se que tanto afecte en cuestion de complejidad espacial y temporal

def long_substring_without_repeat(text_input):
    table_of_character_found = {}
    last_pointer = 0
    size_substring_found = 0

    while last_pointer < len(text_input):
        character = text_input[last_pointer]
        if character in table_of_character_found:
            if len(table_of_character_found) > size_substring_found:
                size_substring_found = len(table_of_character_found)
            table_of_character_found.clear()

        table_of_character_found[character] = last_pointer
        last_pointer += 1

    return size_substring_found

```def long\_substring\_without\_repeat(text\_input):

&#x20;   table\_of\_character\_found = {}

&#x20;   last\_pointer = 0

&#x20;   size\_substring\_found = 0



&#x20;   while last\_pointer < len(text\_input):

&#x20;       character = text\_input\[last\_pointer]

&#x20;       if character in table\_of\_character\_found:

&#x20;           if len(table\_of\_character\_found) > size\_substring\_found:

&#x20;               size\_substring\_found = len(table\_of\_character\_found)

&#x20;           table\_of\_character\_found.clear()



&#x20;       table\_of\_character\_found\[character] = last\_pointer

&#x20;       last\_pointer += 1



&#x20;   return size\_substring\_found

Alberto Perdomo

student•

Mi solucion fue esta pero seguro tiene algo mal:

   sub_dict = {}
   p1 = p2 = 0
   lenght = 0
   while p2 < len(s):
      if s[p2] not in sub_dict.keys():
         lenght = max(lenght, len(sub_dict))
         sub_dict[s[p2]] = lenght
         p2 += 1
      else:
         sub_dict.pop(s[p1])
         p1 += 1

   max_length = max(sub_dict.values())

   return max_length + 1```

Nicolas Alpargatero

student•

No entendí el error del tercer test test_surprise_string 7 ==8. pero bueno funciono con el otro O(n)

Carlos Raúl Romero Martínez

student•

yo lo estoy haciendo en c++ todo y despues con chapt gtp lo convierto en phayton, quiero mejorarn en C y no estoy muy interesado en phyton, dejo mi codiog en c++

#include <bits/stdc++.h>

using namespace std;

string s =
    //"jdkafnlcdsalkxcmpoiuytfccv"
    "abcabcbb"
    ;

bool memo['z' + 10];
int lef = 0,
    answer = 1;

int main()
{

    memo[s[0]] = 1;

    for (int i = 1; i < s.length(); i++)
    {
        if (memo[s[i]] != 0)
        {
            
            for(int j=lef;;j++){
                memo[s[j]]=0;
                if(s[j]==s[i]){
                    
                    lef = j+1;
                    break;
                }
            }
            
        }
        memo[s[i]]=1;
        answer = max(answer, i - lef +1 );    
        //cout<<i<<" "<<lef<<" "<<answer<<endl;
    }

    cout << answer;
    return 0;
}

def lengthOfLongestSubstring(s):
    p1 = p2 = 0
    res = []
    for p1 in range(len(s)):
        count = count_set = 0
        st = set()
        for p2 in range(p1,len(s)):
            st.add(s[p2])
            count_set = len(st)
            count += 1
            if count_set != count:
                break
        res.append(len(st))
    return max(res)

def lengthOfLongestSubstring(s):
    p1 = p2 = 0
    st = set()
    max_length = 0
    
    while p2 < len(s):
        if s[p2] not in st:
            st.add(s[p2])
            max_length = max(max_length, len(st))
            p2 += 1
        else:
            st.remove(s[p1])
            p1 += 1
    
    return max_length

#include<iostream>
#include<string>
#include<unordered_map>

int longest_substring(const std::string &str){

	int longest = 0;
	int p1 = 0;
	int p2 = 0;
	std::unordered_map<char,int> imhere;

	while(p2 < str.size() &&  p1 < str.size()){

		imhere[str[p2]]++;
		if(imhere[str[p2]] == 1){
			p2++;
		}
		else{
			longest = longest > (p2 - p1) ? longest : (p2 - p1);
			imhere[str[p1]] = 0;
			p1++;
		}
	}

	return longest;
}


int main(){

	std::string input = "abcabcbb";
	std::cout << longest_substring(input) << std::endl;

	input = "jdkafnlcdsalkxcmpoiuytfccv";
	std::cout << longest_substring(input) << std::endl;

	return 0;
}

package main

import (
	"fmt"
	"math"
)

func longestSubstring(s string) int {
	var result float64 = 0
	p1 := 0
	chars := make(map[rune]int)

	for p2, char := range s {
		// Si la
		if lastPosition, found := chars[char]; found && lastPosition >= p1 {
			p1 = lastPosition + 1
		}
		chars[char] = p2
		result = math.Max(float64(result), float64(p2-p1+1))
	}

	return int(result)
}

func main() {
	s1 := "abcabcbb"
	fmt.Println(longestSubstring(s1))

	s2 := "jdkafnlcdsalkxcmpoiuytfccv"
	fmt.Println(longestSubstring(s2))
}

def lengthOfLongestSubstring(s):
    char_index = {}  # Diccionario para almacenar la última posición de cada carácter
    left = 0  # Límite izquierdo de la ventana deslizante
    max_length = 0  # Longitud máxima de la subcadena sin repetir
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1  # Mueve el límite izquierdo para evitar repetidos
        
        char_index[s[right]] = right  # Actualiza la última posición del carácter
        max_length = max(max_length, right - left + 1)  # Calcula la longitud máxima
    
    return max_length

def lengthOfLongestSubstring(s):
   # Tu código aquí 👇....

   p1 = 0
   largestLen = 0

   chars = { }

   for p2 , char in enumerate( s ) : 

      if ( char in chars ) : 

         p1 = max( p1, chars[ char ] + 1 ) 

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

      chars[ char ] = p2 


   return largestLen


response = lengthOfLongestSubstring("abcabcbb")
print(response)

response2 = lengthOfLongestSubstring("jdkafnlcdsalkxcmpoiuytfccv")
print(response2)


```def lengthOfLongestSubstring(s):   # Tu código aquí 👇....
&#x20;  p1 = 0   largestLen = 0
&#x20;  chars = { }
&#x20;  for p2 , char in enumerate( s ) :&#x20;
&#x20;     if ( char in chars ) :&#x20;
&#x20;        p1 = max( p1, chars\[ char ] + 1 )&#x20;
&#x20;     largestLen = max( largestLen , ( p2-p1+1) )&#x20;
&#x20;     chars\[ char ] = p2&#x20;

&#x20;  return largestLen

response = lengthOfLongestSubstring("abcabcbb")print(response)
response2 = lengthOfLongestSubstring("jdkafnlcdsalkxcmpoiuytfccv")print(response2)

def long_substring_without_repeat(text_input):
    table_of_character_found = {}
    last_pointer = 0
    size_substring_found = 0

    while last_pointer < len(text_input):
        character = text_input[last_pointer]
        if character in table_of_character_found:
            if len(table_of_character_found) > size_substring_found:
                size_substring_found = len(table_of_character_found)
            table_of_character_found.clear()

        table_of_character_found[character] = last_pointer
        last_pointer += 1

    return size_substring_found

```def long\_substring\_without\_repeat(text\_input):

&#x20;   table\_of\_character\_found = {}

&#x20;   last\_pointer = 0

&#x20;   size\_substring\_found = 0

&#x20;   while last\_pointer < len(text\_input):

&#x20;       character = text\_input\[last\_pointer]

&#x20;       if character in table\_of\_character\_found:

&#x20;           if len(table\_of\_character\_found) > size\_substring\_found:

&#x20;               size\_substring\_found = len(table\_of\_character\_found)

&#x20;           table\_of\_character\_found.clear()

&#x20;       table\_of\_character\_found\[character] = last\_pointer

&#x20;       last\_pointer += 1

&#x20;   return size\_substring\_found

   sub_dict = {}
   p1 = p2 = 0
   lenght = 0
   while p2 < len(s):
      if s[p2] not in sub_dict.keys():
         lenght = max(lenght, len(sub_dict))
         sub_dict[s[p2]] = lenght
         p2 += 1
      else:
         sub_dict.pop(s[p1])
         p1 += 1

   max_length = max(sub_dict.values())

   return max_length + 1```

#include <bits/stdc++.h>

using namespace std;

string s =
    //"jdkafnlcdsalkxcmpoiuytfccv"
    "abcabcbb"
    ;

bool memo['z' + 10];
int lef = 0,
    answer = 1;

int main()
{

    memo[s[0]] = 1;

    for (int i = 1; i < s.length(); i++)
    {
        if (memo[s[i]] != 0)
        {
            
            for(int j=lef;;j++){
                memo[s[j]]=0;
                if(s[j]==s[i]){
                    
                    lef = j+1;
                    break;
                }
            }
            
        }
        memo[s[i]]=1;
        answer = max(answer, i - lef +1 );    
        //cout<<i<<" "<<lef<<" "<<answer<<endl;
    }

    cout << answer;
    return 0;
}

Playground: Longest Substring Without Repeating Characters

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