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

Envío 2198

Problema 0xc9 - Substring más corta con mínimo K caracteres diferentes

  • Autor: Javier
  • Fecha: 2020-11-29 16:54:48 UTC (Hace alrededor de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 2 KBi
#2
Correcto
0.006 s 1 KBi
#3
Incorrecto
0.007 s 2 KBi
#4
Correcto
0.005 s 1 KBi
#5
Correcto
0.005 s 2 KBi
#6
Correcto
0.004 s 1 KBi
#7
Incorrecto
0.006 s 2 KBi
#8
Correcto
0.005 s 2 KBi
#9
Correcto
0.005 s 1 KBi
#10
Correcto
0.082 s 2 KBi
#11
Incorrecto
0.023 s 2 KBi
#12
Correcto
0.087 s 2 KBi
#13
Incorrecto
0.024 s 2 KBi
#14
Correcto
0.113 s 2 KBi
#15
Correcto
0.117 s 2 KBi
#16
Incorrecto
0.023 s 2 KBi
#17
Correcto
0.083 s 2 KBi
#18
Correcto
0.083 s 2 KBi
#19
Correcto
0.069 s 2 KBi
#20
Incorrecto
0.021 s 2 KBi
#21
Correcto
0.093 s 2 KBi
#22
Correcto
0.08 s 2 KBi
#23
Correcto
0.087 s 2 KBi
#24
Correcto
0.081 s 2 KBi
#25
Correcto
0.092 s 2 KBi
#26
Correcto
0.072 s 2 KBi
#27
Correcto
0.078 s 2 KBi
#28
Correcto
0.079 s 2 KBi
#29
Correcto
0.078 s 2 KBi
#30
Correcto
0.022 s 1 KBi
#31
Correcto
0.025 s 2 KBi
#32
Correcto
0.033 s 2 KBi
Puntos totales: 82 / 100

Código

#include <iostream>
#include <map>
#include <bits/stdc++.h>
using namespace std;

int main() {
    string word;
    int k;
    cin >> word >> k;
    
    map<char, int> map_count;
    int left = 0;
    int shortest = INT_MAX;
    for (int right = 0; right < word.size(); right++) {
        char letter = word[right];
        map_count[letter]++;
        while (map_count.size() >= k) {
            shortest = min(shortest, right - left + 1);
            char left_char = word[left];
            map_count[left_char]--;
            if (map_count[left_char] == 0) {
                map_count.erase(left_char);
            }
            left++;
        }
        

    }
    cout << shortest << endl;
}