Dada una cadena, encuentre la longitud de la subcadena más larga sin caracteres repetidos. Por ejemplo, la subcadena más larga sin letras repetidas para «abcabcbb» es «abc», cuya longitud es 3. Para «bbbbb», la subcadena más larga es «b», con la longitud de 1.
Análisis
La idea básica para resolver este problema es utilizar una estructura de datos adicional para rastrear los caracteres únicos en una ventana deslizante. Tanto una matriz como un conjunto de hash funcionan para este propósito.
Solución Java 1
La primera solución es como el problema de «determinar si una cadena tiene todos los caracteres únicos» en CC 150. Podemos usar una matriz de banderas para rastrear los caracteres existentes para la subcadena más larga sin caracteres repetidos.
public int lengthOfLongestSubstring(String s) { if(s==null) return 0; boolean[] flag = new boolean[256]; int result = 0; int start = 0; char[] arr = s.toCharArray(); for (int i = 0; i < arr.length; i++) { char current = arr[i]; if (flag[current]) { result = Math.max(result, i - start); // the loop update the new start point // and reset flag array // for example, abccab, when it comes to 2nd c, // it update start from 0 to 3, reset flag for a,b for (int k = start; k < i; k++) { if (arr[k] == current) { start = k + 1; break; } flag[arr[k]] = false; } } else { flag[current] = true; } } result = Math.max(arr.length - start, result); return result; } |
Solución Java 2 – HashSet
Usar un HashSet puede simplificar mucho el código.
/* pwwkew i | j | i | j | i | j | */ public int lengthOfLongestSubstring(String s) { if(s==null||s.length()==0){ return 0; } HashSet<Character> set = new HashSet<>(); int result = 1; int i=0; for(int j=0; j<s.length(); j++){ char c = s.charAt(j); if(!set.contains(c)){ set.add(c); result = Math.max(result, set.size()); }else{ while(i<j){ if(s.charAt(i)==c){ i++; break; } set.remove(s.charAt(i)); i++; } } } return result; } |
