Решение задачи "Красивая строка" с Codeforces

С пояснением   Просмотров: 36


Строка называется красивой, если никакие два последовательных символа строки не равны. Например, строки «ababcb», «a» и «abab» красивые, тогда как «aaaaaa», «abaa» и «bb» нет.

Ahcl хочет построить красивую строку. У него есть строка s, состоящая только из символов 'a', 'b', 'c' и '?'. Ahcl должен поменять каждый символ '?' на один из трех символов 'a', 'b' или 'c', так что получившаяся строка будет красивой. Помогите ему!

Более формально, после замены всех символов '?', условие si≠si+1 должно быть выполнено для всех 1≤i≤|s|−1, где |s| это длина строки s.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    string s;
    string a = "abc";
    while(t--){
        cin >> s;
        s.insert(0, 1, 'd');
        s+='e';
        for(int i = 1; i < s.size() - 1; ++i){
            if(s[i] == '?'){
                char prv = s[i - 1], nxt = s[i + 1];
                for(int j = 0; j < a.size(); ++j)
                    if(a[j] != prv && a[j] != nxt)
                        s[i] = a[j];
            }
        }
        bool b = true;
        for(int i = 0; i < s.size(); ++i)
            if(s[i] == s[i + 1]){
                cout << -1 << endl;
                b = false;
                break;
            }
        s.erase(0, 1);
        s.pop_back();
        if(b)
            cout << s << endl;
    }

}

         

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


Если строка s изначально содержит 2 одинаковые последовательные буквы («aa», «bb» или «cc»), то ответ, очевидно, равен -1.

В противном случае всегда можно заменить все символы '?' сделать ее красивой. Мы заменим один '?' в любое время и в любом порядке (например, слева направо). Для каждого «?», Поскольку он смежен не более чем с 2 другими символами, и у нас есть 3 варианта («a», «b» и «c») для этого «?», Всегда существует хотя бы один вариант, который отличается от 2 символа, которые соседствуют с этим '?'. Просто найдите и замените '?' по этому.

Временная сложность: O (n), где n - длина s.

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

Комментарии

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