█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6238

Problema 0x59 - Substring más larga con máximo K caracteres diferentes

  • Autor: rpedrazacoello
  • Fecha: 2022-05-27 02:04:51 UTC (Hace casi 2 años)
Caso # Resultado Tiempo Memoria
#1
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#2
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#3
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#4
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#5
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#6
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#7
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#8
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#9
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#10
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#11
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#12
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#13
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#14
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#15
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#16
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#17
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#18
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#19
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#20
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#21
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#22
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#23
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
#24
Error de compilación 
                      Main.java:5: error: class SubstringMasLargaMaximoKCaracteresDiferentes is public, should be declared in a file named SubstringMasLargaMaximoKCaracteresDiferentes.java
public class SubstringMasLargaMaximoKCaracteresDiferentes {
       ^
1 error
Puntos totales: 0 / 100

Código

import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;

public class SubstringMasLargaMaximoKCaracteresDiferentes {
    private static HashMap<Integer, Integer> memoization = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String word = scanner.nextLine();
        char[] wordArray = word.toCharArray();

        int k = scanner.nextInt();

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < wordArray.length; i++) {
            HashMap<Character, Integer> knownCharacters = new HashMap<>();
            int localMax = longestSubstringWithAtMostKDifferentCharactersStartingAtX(i, wordArray, k, knownCharacters);

            if(localMax>max){
                max=localMax;
            }
        }

        System.out.println(max);
    }

    private static int longestSubstringWithAtMostKDifferentCharactersStartingAtX(int x, char[] word, int k, HashMap<Character, Integer> knownCharacters) {
        if(memoization.containsKey(Objects.hash(x, k))){
            return memoization.get(Objects.hash(x, k));
        }

        if (x == word.length || (k<=0 && !knownCharacters.containsKey(word[x]))) {
            memoization.put(Objects.hash(x, k), 0);
            return 0;
        }


        if (!knownCharacters.containsKey(word[x])) {
            k--;
            knownCharacters.put(word[x], 1);
        }

        int max = 1 + longestSubstringWithAtMostKDifferentCharactersStartingAtX(x + 1, word, k, knownCharacters);
        memoization.put(Objects.hash(x, k), max);
        return max;
    }
}