Mã C ++ để nhận chuỗi cập nhật có cùng số lượng 'a' và 'b'

Giả sử chúng ta có chuỗi S với độ dài chẵn n. S chỉ chứa hai loại ký tự 'a' và'b '. Chúng tôi muốn sửa đổi chuỗi để mọi tiền tố có độ dài của nó đều có số lượng bản tin 'a' và 'b' bằng nhau. Để đạt được điều đó, chúng ta có thể thực hiện thao tác sau với số lần tùy ý:Chọn một số vị trí trong chuỗi của mình và thay thế ký tự trên vị trí này bằng ký tự khác. Trả lại chuỗi đã cập nhật.

Vì vậy, nếu đầu vào là S ="aabbbb", thì đầu ra sẽ là "baabab"

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

"aabbbb"

Đầu ra

baabab