Cập nhật chuỗi a,b sao cho mọi tiền tố có số a,b bằng nhau bằng C++

Mô tả bài toán

Chuỗi S độ dài chẵn chỉ chứa 'a','b'. Sửa đổi ít nhất (thay ký tự) sao cho mọi tiền tố độ dài chẵn có số 'a' = số 'b'. Trả về chuỗi sau sửa.

Ví dụ

S="aabbbb" → Output: "baabab".

Thuật toán

Xét từng cặp (i,i+1) với i chẵn. Nếu S[i]==S[i+1] thì đổi S[i] (a→b hoặc b→a). Điều này đảm bảo mỗi cặp có 1 a và 1 b, nên mọi tiền tố chẵn cân bằng.

Code C++

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

string solve(string S) {
    int n = S.size();
    for (int i = 0; i < n; i += 2) {
        if (S[i] == S[i+1]) {
            S[i] = (S[i] == 'a') ? 'b' : 'a';
        }
    }
    return S;
}

int main() {
    string S = "aabbbb";
    cout << solve(S) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: "aabbbb"

Output: "baabab"