โค้ด C++ อัปเดตสตริงให้จำนวน a และ b เท่ากันในทุก prefix

สมมติว่าเรามีสตริง S ความยาว n คู่ S มีแค่ 'a' และ 'b' ต้องการแก้ไขสตริงให้ทุก prefix ที่มีความยาวคู่ มีจำนวน 'a' และ 'b' เท่ากัน สามารถดำเนินการได้ไม่จำกัด: เลือกตำแหน่งในสตริง แทนที่ตัวอักษรด้วยอีกตัว คืนสตริงที่แก้ไขแล้ว

เช่น ถ้าอินพุตคือ S = "aabbbb" เอาต์พุตจะเป็น "baabab"

ขั้นตอนการแก้ปัญหา

n := ขนาดของ S
for i := 0 ถึง n-1 ก้าว 2:
    if S[i] == S[i+1]:
        เพิ่ม ans ขึ้น 1
        S[i] := (ถ้า S[i] == 'a' แล้ว 'b' มิฉะนั้น 'a')
return S

ตัวอย่างโค้ด

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

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

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

อินพุต

"aabbbb"

เอาต์พุต

baabab