Решение задачи "Дополни слово" с Codeforces

Без пояснения   Просмотров: 10


Кодер ZS любит читать словарь. Он считает, что слово хорошее, если найдется его подстрока (непрерывный отрезок букв) длины 26 такая, что она содержит каждую букву латинского алфавита ровно по одному разу. В частности, если длина строки строго меньше 26, такой подстроки не существует и строка не является хорошей.

Теперь Кодер ZS сообщил вам слово, в котором некоторые буквы пропущены, так как он забыл их. Он хочет определить, возможно ли вставить пропущенные буквы так, что слово станет хорошим. Если это возможно, ему нужно найти пример такого слова. Поможете ему?

Код

#include <bits/stdc++.h>

using namespace std;

int abc[26];

bool good(){
	for(int i = 0; i < 26; i++){
		if(abc[i] > 1) return false;
	}
	
	return true;
}

string fill(string s, int start){
	int i = 0, j = start;
	
	while(i < 26 and j < start + 26){
		if(abc[i] == 0 and s[j] == '?'){
			s[j] = i + 'A';
			i++; j++; continue;
		}
		if(abc[i] != 0) i++;
		if(s[j] != '?') j++;
	}
	
	
	for(char &c : s){
		if(c == '?') c = 'A';
	}
	
	return s;
}


int main(){
	
	string s; cin >> s;
	
	int n = s.size();
	
	for(auto e : s.substr(0, 26)) abc[e - 'A']++;
	
	for(int i = 0; i <= n - 26; i++){
		if(good()){
			cout << fill(s, i) << endl; return 0;
		}
		if(s[i] != '?') abc[s[i] - 'A']--;
		if(i + 26 < n and s[i + 26] != '?') abc[s[i + 26] - 'A']++;
	}

	cout << -1 << endl;

	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться