สมมติว่าเรามีสตริง S ที่มีความยาวเท่ากัน n S มีอักขระเพียงสองประเภทคือ 'a' และ 'b' เราต้องการแก้ไขสตริงเพื่อให้ทุกคำนำหน้ามีความยาวมีจำนวนตัวอักษร 'a' และ 'b' เท่ากัน เพื่อให้บรรลุสิ่งนั้น เราสามารถดำเนินการตามจำนวนครั้งได้โดยพลการ:เลือกตำแหน่งบางตำแหน่งในสตริงของเขาและแทนที่ตัวอักษรในตำแหน่งนี้ด้วยตัวอักษรอื่น ส่งคืนสตริงที่อัปเดต
ดังนั้น หากอินพุตเป็น S ="aabbbb" ผลลัพธ์จะเป็น "baabab"
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
n := size of S for initialize i := 0, when i < n, update i := i + 2, do: if S[i] is same as S[i + 1], then: (increase ans by 1) S[i] := (if S[i] is same as 'a', then 'b', otherwise '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
