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

Envío 2199

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

  • Autor: Javier
  • Fecha: 2020-11-29 16:56:20 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 1 KBi
#2
Correcto
0.005 s 2 KBi
#3
Correcto
0.005 s 2 KBi
#4
Correcto
0.004 s 2 KBi
#5
Correcto
0.004 s 2 KBi
#6
Correcto
0.004 s 1 KBi
#7
Correcto
0.004 s 1 KBi
#8
Correcto
0.005 s 2 KBi
#9
Correcto
0.005 s 2 KBi
#10
Correcto
0.103 s 2 KBi
#11
Correcto
0.016 s 2 KBi
#12
Correcto
0.082 s 2 KBi
#13
Correcto
0.02 s 2 KBi
#14
Correcto
0.079 s 2 KBi
#15
Correcto
0.087 s 2 KBi
#16
Correcto
0.025 s 2 KBi
#17
Correcto
0.087 s 2 KBi
#18
Correcto
0.064 s 2 KBi
#19
Correcto
0.059 s 2 KBi
#20
Correcto
0.02 s 2 KBi
#21
Correcto
0.087 s 2 KBi
#22
Correcto
0.08 s 2 KBi
#23
Correcto
0.079 s 2 KBi
#24
Correcto
0.087 s 2 KBi
#25
Correcto
0.079 s 2 KBi
#26
Correcto
0.085 s 2 KBi
#27
Correcto
0.079 s 2 KBi
#28
Correcto
0.072 s 2 KBi
#29
Correcto
0.075 s 2 KBi
#30
Correcto
0.025 s 2 KBi
#31
Correcto
0.028 s 2 KBi
#32
Correcto
0.028 s 2 KBi
Puntos totales: 100 / 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++;
        }
    }
    if (shortest == INT_MAX){
        cout << -1 << endl;
    } else {
        cout << shortest << endl;
    }
}