Este es un problema solicitado por Google.
Dada una cadena, busque la subcadena más larga que contenga solo dos caracteres únicos. Por ejemplo, dado «abcbbbbcccbdddadacb», la subcadena más larga que contiene 2 caracteres únicos es «bcbbbbcccb».
1. Subcadena más larga que contiene 2 caracteres únicos
En esta solución, se usa un mapa hash para rastrear los elementos únicos en el mapa. Cuando se agrega un tercer carácter al mapa, el puntero izquierdo debe moverse hacia la derecha.
Puede utilizar «abac» para recorrer esta solución.
public int lengthOfLongestSubstringTwoDistinct(String s) { int max=0; HashMap<Character,Integer> map = new HashMap<Character, Integer>(); int start=0; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(map.containsKey(c)){ map.put(c, map.get(c)+1); }else{ map.put(c,1); } if(map.size()>2){ max = Math.max(max, i-start); while(map.size()>2){ char t = s.charAt(start); int count = map.get(t); if(count>1){ map.put(t, count-1); }else{ map.remove(t); } start++; } } } max = Math.max(max, s.length()-start); return max; } |
Ahora bien, si esta pregunta se amplía para ser «la subcadena más larga que contiene k caracteres únicos», ¿qué debemos hacer?
2. Solución para K caracteres únicos
Se corrige la siguiente solución. Dado «abcadcacacaca» y 3, devuelve «cadcacacaca».
public int lengthOfLongestSubstringKDistinct(String s, int k) { int result = 0; int i=0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); for(int j=0; j<s.length(); j++){ char c = s.charAt(j); if(map.containsKey(c)){ map.put(c, map.get(c)+1); }else{ map.put(c, 1); } if(map.size()<=k){ result = Math.max(result, j-i+1); }else{ while(map.size()>k){ char l = s.charAt(i); int count = map.get(l); if(count==1){ map.remove(l); }else{ map.put(l, map.get(l)-1); } i++; } } } return result; } |
El tiempo es O (n).
