Algoritmo de Ventana Deslizante para Subcadenas Únicas

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

Resumen

¿Cómo comprender la entrada del problema?

Antes de abordar cualquier problema de programación, es crucial entender a fondo la entrada. En este caso, la entrada es simplemente un string, o cadena de caracteres. No se debe asumir respuestas sin verificar aspectos importantes como la posible presencia de caracteres duplicados; por ejemplo, no se toma en cuenta si letras mayúsculas y minúsculas deben considerarse iguales. Siempre debemos contemplar todas las características de nuestras entradas de datos.

¿Cuál es la longitud de la cadena más larga sin caracteres repetidos?

El objetivo es identificar la longitud de la cadena más larga en la que no se repita ningún carácter. El problema puede parecer sencillo a primera vista. Sin embargo, la eficiencia en el cálculo es clave. Crear todos los posibles grupos de caracteres y elegir el más largo no es viable. Entonces, trabajemos en recorrer el arreglo una sola vez para optimizar el tiempo de ejecución, buscando una solución de complejidad temporal O(N).

¿Cómo se implementa el patrón de ventana deslizante?

El patrón de ventana deslizante, esencial para este problema, utiliza dos apuntadores en un arreglo para evaluar condiciones sin modificar el orden de los datos. El primero inicia al comienzo y el segundo se mueve mientras no se encuentre un duplicado. Este método es especialmente útil cuando se busca medir distancias o retornar grupos de letras en listas de datos organizados consecutivamente.

¿Cómo identificar duplicados programáticamente?

Para detectar duplicados de forma programática, una lista puede almacenar las letras ya encontradas. Sin embargo, iterar esta lista para cada letra nueva resultaría en una solución poco eficiente de complejidad O(N^2). En cambio, podemos utilizar una estructura de datos que permita acceder a los valores en O(1), como un hash table, para almacenar cada letra como llave y su posición en el string.

¿Qué ventajas ofrece un hash table en este contexto?

El uso de un hash table proporciona eficaces accesos y actualizaciones en O(1). Cuando se encuentra un duplicado, no es necesario volver al principio; el apuntador del inicio se mueve detrás de la última posición de la letra repetida. Este método asegura una mayor eficiencia espacial utilizando hasta la longitud de los caracteres únicos y una eficiencia temporal de O(N), recorriendo el string una sola vez para encontrar la subcadena más larga.

¿Por qué es vital considerar la eficiencia en programación?

La eficiencia no solo se trata del tiempo de ejecución, sino también del uso de recursos como la memoria. En entrevistas o evaluaciones, los entrevistadores pueden priorizar soluciones más rápidas aunque requieran más espacio. Es crucial comprender también qué se prefiere sacrificar: tiempo o espacio. Evaluar, comparar y justificar tus decisiones en base a estos atributos es esencial en el diseño de soluciones óptimas y efectivas.

Luis Sandoval

student•

Aporto mi posible 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;
    }

Nicolas Alpargatero

student•

El p2 como se mueve constante con enumerate() funciona. El usar max o min no afecta la Big O. El p2 - p1 + 1 es porque es inclusivo y toca tener en cuenta el valor inicial y final.

Crumble Coder

student•

Curioso que un curso donde se enseña a optimizar código es el curso que va a saltos y no lo pueda ver de forma fluida. Da igual desde qué servidor lo vea (A,B o C) ¿Pueden optimizar esto?

Angel Agustín Hernandez Soledad

student•

Aporto solucion en Java:```js class Solution { public int lengthOfLongestSubstring(String s) {

    if(s.length() == 0) {
        return 0;
    } else if(s.length() == 1) {
        return 1;
    }
    
    Map<Character, Integer> tmp = new HashMap<>();
    int p1 = 0;
    int p2 = 0;
    int maxLength = 0;

    while(p2 <= s.length() - 1) {
        char val1 = s.charAt(p1);
        char val2 = s.charAt(p2);

        if(!tmp.containsKey(val2)) {
            tmp.put(val2, 0);
            p2++;
        } else {
            tmp.remove(val1);
            p1++;
        }
        maxLength = Math.max(maxLength, p2 - p1);
    }

    return maxLength;
}

}

Andres Silva Vega

student•

Me parece confusa la explicación. Ya habiéndolo entendido en otro lado para mi el diccionario de datos o hash table es clave en este ejercicio porque permite ubicar un dato como si este fuera un índicel, es decir sin recorrer el set de letras encontradas, generando una búsqueda de O(1). Tampoco me gusta que las explicaciones las deje a medias. Si propone un string "abcabcc" lo que veo es que no explica el algoritmo completo, no llega hasta la última "c" sino que da por sentado que al explicar un pedazo es suficiente y a veces no

Rosmer Hernández

student•

const subsString = (string) => {
  let p1 = 0;
  let p2 = 0;
  let result = 0;
  let auxMap = new Map();

  while (p2 < string.length) {
    let letter = string[p2];
    if (!auxMap.has(letter)) {
      auxMap.set(letter, 1);
      p2++;
    } else {
      result = Math.max(result, p2 - p1);
      auxMap.clear();
      p1 = p2;
    }
  }

  return result;
};

Miguel Angel Reyes Moreno

student•

Propongo mi solución en Python antes de ver el vídeo:

def longest\_substring\_without\_repeating\_characters(text) -> int:  if len(text) == 0:    return 0
&#x20; seen = \[]  p1, p2, longitud, longitud\_maxima = 0,0,0,0
&#x20; while p2 < len(text) - 1:    if text\[p2] not in seen:      seen.append(text\[p2])      p2 += 1    if text\[p2] in seen:      p1 = p2      longitud = len(seen)      if longitud > longitud\_maxima:        longitud\_maxima = longitud      seen.clear()
&#x20; return longitud\_maxima

if *\_\_name\_\_* == '\_\_main\_\_':  print(longest\_substring\_without\_repeating\_characters("abcabcbbz")) #\* 3  print(longest\_substring\_without\_repeating\_characters("jdkafnlcdsalkxcmpoiuytfccv")) #\* 15

Isaí Sánchez Jiménez

student•

Otra posible solución con set seria la siguiente

Empezamos con un set vacio { } MaxLen = 0

checamos si la letra a la que apunta el p2 esta en el set, si no pues la agregamos y movemos p2 e incializamos una variable para almacenar la mayor longitud que empieza en 0 llamada MaxLen

{”a”} MaxLen = 1

{”a”,”b”} MaxLen = 2

{”a”,”b”,”c”} MaxLen = 3

al encontrar una letra repetida, p1 va a eliminar la letra a la que esta apuntando y moverse un lugar y p2 tambien se mueve

{”b”,”c”} MaxLen = 3

{”c”} MaxLen = 3

{ } MaxLen = 3

llenando y vaciando el set según la repetición de las letras y quedándonos con la mayor longitud de la cadena encontrada, para al final devolverla.

Isaí Sánchez Jiménez

student•

revisando solo una vez la lista y con O(n) :D

Hans Arias

student•

Siempre me puso a pensar en muchas formas, pero esta es una posible solución


    // a, b, c, a, b, c, b, b
    public int countWithoutRepeating (String s) {
        if (s.length() < 2) return 0;

        int currentCount = 0;
        int maxCount = 0;

        int pointerA = 0;
        int pointerB = 0;

        for (int i = 0; i < s.toCharArray().length; i++) {
            // B

            boolean repeated = false;
            int j = pointerA; // 6
            // 6 < 7
            while (j < pointerB) {
                // b == b
                if (s.charAt(j) == s.charAt(i)) {
                    repeated = true;
                    break;
                }

                j++;
            }

            // 3 --> 3, 1
            maxCount = Math.max(maxCount, currentCount);

            // true
            if (repeated) {
                currentCount = 0;
                pointerA = pointerB; // 7
            }

            currentCount++; // 1
            pointerB++; // 8
        }

        return maxCount;
    }

Test.

public class LongestSubstringTest {

    LongestSubstring object = new LongestSubstring();

    @Test
    public void shouldBeThreeByABC () {
        String s = "abcabcbb";
        assertEquals(3,object.countWithoutRepeating(s));
    }

    @Test
    public void shouldBeFifteen () {
        String s = "jdkafnlcdsalkxcmpoiuytfccv";
        assertEquals(15,object.countWithoutRepeating(s));
    }

}

Victor Hugo Vázquez Gómez

student•

Lo mas enredado es saber cuando mover el pointer que casi no se mueve hehe:

Mi solucion en TypeScript:

export const longestSubstringWithoutRepeatingChars = (s: string): number => {
  let substring: { [key: string]: number } = {};
  let prevMaxValue = 0;
  let p1 = 0;
  let p2 = 0;

  while (p2 < s.length) {
    const char = s[p2];

    if (substring[char] !== undefined) {
      if (substring[char] >= p1) {
        prevMaxValue = Math.max(prevMaxValue, (p2 - p1));

        p1 = substring[char] + 1;
        substring[char] = p2;
        p2++;
      } else {
        substring[char] = p2;
        p2++;
      }
    } else {
      substring[char] = p2;
      p2++;
    }
  }

  return Math.max(prevMaxValue, (p2 - p1));
};

Victor Hugo Vázquez Gómez

student•

Se puede mejorar el codigo ya que estoy asignando el indice al objeto e iterando p2 en tres lugares.

Juan Pablo Reina Gutierrez

student•

def longest_sub_without_repeating_chars(txt):
    # Pueden haber duplicados en este contexto.
    # Todo se convierte a mínusculas.
    l_txt = list(txt)
    ap1 = 0 # Apunta al inicio de la subcadena más larga
    ap2 = 0 # Apunta al final de la subcadena más larga
    dict_comb = {} # Almacena el índice de las letras por cada subcadena
    mayor_tam = 1 # Mayor tamaño a retornar

    while ap2 < len(l_txt):
        if l_txt[ap2] in dict_comb:
            if ap2 - ap1 > mayor_tam:
                mayor_tam = ap2 - ap1

            ap1 = ap2
            dict_comb = {} # Vaciar el diccionario para guardar los índices
            #  de la siguiente subcadena

        dict_comb[l_txt[ap2]] = ap2
        ap2 += 1

    return mayor_tam

    # Si por ejemplo tenemos una solución que en espacio es o(n^2), pero
    #  en performance es rápida, es bueno preguntar al entrevistador si
    #  está bien presentarla así. Es decir cual es el atributo de calidad a
    #  priorizar

txt = "abcabcbb"
sal = longest_sub_without_repeating_chars(txt)
print(sal)

txt = "jdkafnlcdsalkxcmpoiuytfccv"
sal = longest_sub_without_repeating_chars(txt)
print(sal)

txt = "jdkafnlcdsalkxcmpoiuytfavadswlkxcmpoiuytfñazadsalkxcmpoiuytf"
sal = longest_sub_without_repeating_chars(txt)
print(sal)

Ivo Zayas

student•

comparto mis solución en 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
}