LeetCode: subcadena más larga con al menos K caracteres repetidos (Java)

Encuentre la longitud de la subcadena T más larga de una cadena dada (consta de letras minúsculas solamente) de modo que cada carácter en T aparezca no menos de k veces.

Ejemplo 1:

Input:
s = "aaabb", k = 3

Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.

Solución Java

Este problema se puede resolver usando DFS. Cuando todos los caracteres en la cadena de entrada ocurren> = k, devuelve la longitud. Pero primero necesitamos dividir la cadena de entrada usando los caracteres cuya ocurrencia

public int longestSubstring(String s, int k) {
    HashMap<Character, Integer> counter = new HashMap<Character, Integer>();
 
    for(int i=0; i<s.length(); i++){
 
        char c = s.charAt(i);
        if(counter.containsKey(c)){
            counter.put(c, counter.get(c)+1);
        }else{
            counter.put(c, 1);
        }
 
    }
 
    HashSet<Character> splitSet = new HashSet<Character>();
    for(char c: counter.keySet()){
        if(counter.get(c)<k){
            splitSet.add(c);
        }
    }
 
    if(splitSet.isEmpty()){
        return s.length();
    }
 
    int max = 0;
    int i=0, j=0;
    while(j<s.length()){
        char c = s.charAt(j);
        if(splitSet.contains(c)){
            if(j!=i){
                max = Math.max(max, longestSubstring(s.substring(i, j), k));
            }
            i=j+1;
        }
        j++;
    }
 
    if(i!=j)
         max = Math.max(max, longestSubstring(s.substring(i, j), k));
 
    return max;
}

Deja una respuesta

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta