Chuỗi không có AAA hoặc BBB trong C ++

Giả sử chúng ta có hai số nguyên A và B, chúng ta phải trả về bất kỳ chuỗi S nào, sao cho -

• S có độ dài A + B và chứa chính xác A số chữ cái ‘a’ và B số chữ cái ‘b’.

• Chuỗi con “aaa” và “bbb” sẽ không có trong chuỗi S

Vì vậy, nếu các số nguyên đã cho là A =4, B =1, thì kết quả sẽ là "aabaa".

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

• Xác định một chuỗi ret, ban đầu chuỗi này trống

• trong khi | A - B |> =2,

  • nếu A> B, thì

    • ret:=ret nối ‘aa’

    • giảm A đi 2

    • nếu B khác 0, hãy nối ‘b’ với ret và giảm B đi 1

  • khác

    • ret:=ret nối ‘bb’

    • giảm B đi 2

    • nếu A khác 0, hãy nối ‘a’ với ret và giảm A đi 1

• trong khi A khác 0 hoặc B khác 0

  • nếu A khác 0 và (kích thước của ret <2 hoặc không bằng (kích thước của ret> =2 và phần tử cuối cùng của ret =phần tử cuối cùng thứ hai của ret) và phần tử cuối cùng của ret là ‘a’), thì

    • ret:=ret + ‘a’, giảm A đi 1

    • nếu B khác 0

      • ret:=ret nối ‘b’, giảm B đi 1

    • nếu không thì ret nối ‘b’, giảm B đi 1, nếu A không phải 0, thì nối a với ret và giảm A đi 1

• trả lại ret

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string strWithout3a3b(int A, int B) {
      string ret = "";
      while(abs(A - B) >= 2){
         if(A > B){
            ret += 'a';
            ret += 'a';
            A -= 2;
            if(B) {
               ret += 'b';
               B--;
            }
         }else{
            ret += 'b';
            ret += 'b';
              B -= 2;
              if(A) {
               ret += 'a';
               A--;
            }
         }  
     }
      while(A || B){
         if(A && (ret.size() < 2 || !(ret.size() >= 2 && ret[ret.size() - 1] == ret[ret.size() -                2] && ret[ret.size() - 1] == 'a') ) ){
            ret += 'a';
            A--;
            if(B) {
               ret += 'b';
               B--;
            }
         }else{
            ret += 'b';
            B--;
            if(A) {
              ret += 'a';
              A--;
            }
         }      
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.strWithout3a3b(4, 1));
}

Đầu vào

4
1

Đầu ra

"aabaa"