สตริงที่ไม่มี AAA หรือ BBB ใน C++

สมมติว่าเรามีจำนวนเต็ม A และ B สองจำนวน เราต้องส่งคืนสตริง S ใด ๆ เช่นนั้น -

• S มีความยาว A + B และประกอบด้วยตัวอักษร 'a' และหมายเลข 'b' จำนวน A อย่างแน่นอน

• สตริงย่อย “aaa” และ “bbb” จะไม่อยู่ในสตริง S

ดังนั้นหากจำนวนเต็มที่กำหนดให้คือ A =4, B =1 ผลลัพธ์จะเป็น “aabaa”

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสตริง ret เริ่มแรกว่างเปล่า

• ในขณะที่ |A – B|>=2,

  • ถ้า A> B แล้ว

    • ret :=ret เชื่อม 'aa'

    • ลด A ลง 2

    • ถ้า B ไม่เท่ากับศูนย์ เชื่อม 'b' กับ ret และลด B ขึ้น 1

  • อื่นๆ

    • ret :=ret concatenate 'bb'

    • ลด B ขึ้น 2

    • ถ้า A ไม่เป็นศูนย์ เชื่อม 'a' กับ ret และลด A ลง 1

• ขณะที่ A ไม่เป็นศูนย์ หรือ B ไม่ใช่ศูนย์

  • ถ้า A ไม่ใช่ศูนย์และ (ขนาดของ ret <2 หรือไม่ของ (ขนาดของ ret>=2 และองค์ประกอบสุดท้ายของ ret =องค์ประกอบสุดท้ายที่สองของ ret) และองค์ประกอบสุดท้ายของ ret คือ 'a') ดังนั้น

    • ret :=ret + 'a' ลด A ลง 1

    • ถ้า B ไม่ใช่ศูนย์

      • ret :=ret concatenate 'b', ลด B ขึ้น 1

    • มิฉะนั้น ret concatenate 'b' ลด B ขึ้น 1 ถ้า A ไม่ใช่ 0 จากนั้นเชื่อม a กับ ret และลด A ลง 1

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

4
1

ผลลัพธ์

"aabaa"