Encuentra la subcadena más larga sin repetir caracteres

Es imprescindible entender el código correctamente antes de utilizarlo a tu proyecto y si tdeseas aportar algo puedes dejarlo en la sección de comentarios.

Solución:

1. Necesitará un localizador de inicio y final (/puntero) para el
   string y un array donde almacena información para cada personaje: ¿ocurrió al menos una vez?

2. Empezar al principio de la stringambos localizadores apuntan al inicio de la string.

3. Mueva el localizador final hacia la derecha hasta que encuentre una repetición (o llegue al final del string). Para cada carácter procesado, guárdelo en el array. Cuando se detenga, almacene la posición si esta es la subcadena más grande. Recuerda también el carácter repetido.

4. Ahora haga lo mismo con el localizador de inicio, al procesar cada carácter, elimine sus banderas del array. Mueva el localizador hasta que encuentre la aparición anterior del carácter repetido.

5. Vuelva al paso 3 si no ha llegado al final de string.

Total: O(N)

import java.util.HashSet;

public class SubString 
    public static String subString(String input)

        HashSet set = new HashSet();

        String longestOverAll = "";
        String longestTillNow = "";

        for (int i = 0; i < input.length(); i++) 
            char c = input.charAt(i);

            if (set.contains(c)) 
                longestTillNow = "";
                set.clear();
            
            longestTillNow += c;
            set.add(c);
            if (longestTillNow.length() > longestOverAll.length()) 
                longestOverAll = longestTillNow;
            
        

        return longestOverAll;
    

    public static void main(String[] args) 
        String input = "substringfindout";
        System.out.println(subString(input));
    

mantienes un array indicando la posición en la que un cierto carácter apareció por última vez. Por conveniencia, todos los caracteres ocurrieron en la posición -1. Usted itera sobre el string manteniendo una ventana, si un carácter se repite en esa ventana, se corta el prefix que finaliza con la primera aparición de este carácter. En todo momento, mantienes la longitud más larga. Aquí hay una implementación de python:

def longest_unique_substr(S):
  # This should be replaced by an array (size = alphabet size).
  last_occurrence =  
  longest_len_so_far = 0
  longest_pos_so_far = 0
  curr_starting_pos = 0
  curr_length = 0

  for k, c in enumerate(S):
    l = last_occurrence.get(c, -1)
    # If no repetition within window, no problems.
    if l < curr_starting_pos: 
        curr_length += 1
    else:
        # Check if it is the longest so far
        if curr_length > longest_len_so_far: 
            longest_pos_so_far = curr_starting_pos
            longest_len_so_far = curr_length
        # Cut the prefix that has repetition
        curr_length -= l - curr_starting_pos
        curr_starting_pos = l + 1
    # In any case, update last_occurrence
    last_occurrence[c] = k

  # Maybe the longest substring is a suffix
  if curr_length > longest_len_so_far:
    longest_pos_so_far = curr_starting_pos
    longest_len_so_far = curr_length

  return S[longest_pos_so_far:longest_pos_so_far + longest_len_so_far]

Recuerda que puedes difundir este enunciado si te valió la pena.

---

---

Utiliza Nuestro Buscador