Республиканская олимпиада по информатике, 2015 год, 9 класс

Задача B. Буквы

Задается строка $S$, состоящая из строчных букв английского алфавита. Найдите в ней подстроку наименьшей длины, в которую входят ровно $K$ различных букв, и выведите ее длину.

Входные данные

В первой строке входного файла задается одна строка $S$, состоящая из строчных букв английского алфавита. Во второй строке задается одно целое положительное число $K$ ($1\le K \le 26$).

Выходные данные

Выведите ответ к задаче или -1, если такой подстроки не существует.

Примеры

aaabbccc
3

Ответ:

4

Оценивание:

Данная задача содержит три подзадачи:
длина строки $S \le 100$. Оценивается в $20$ баллов.
длина строки $S \le 5000$. Оценивается в $30$ баллов.
длина строки $S \le 10^5$. Оценивается в $50$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Ержан Уткелбаев )

Комментарий/решение

#include <iostream>

using namespace std;

int main() {

string s;

int k;

cin >> s;

cin >> k;

if(k == s.size()){

cout << k;

return 0;

}

int a[s.size()+1];

a[0] = 1;

for(int i = 1; i < s.size(); i++){

if(s[i] == s[i - 1]){

a[i] = a[i - 1];

}else{

a[i] = a[i - 1] + 1;

}

}

int mn = s.size();

int j;

for(int i = 0; i < s.size(); i++){

if(a[i] >= k){

j = i;

while(a[j] != a[i] - k + 1) {

j--;

}

if (mn > i - j + 1) {

mn = i - j + 1;

}

}

if (mn == k) {

cout << mn;

return 0;

}

}

cout << mn;

return 0;

}