String Without AAA or BBB ใน C++

คำอธิบายปัญหา

กำหนดจำนวนเต็ม A และ B ต้องการสร้างสตริง S ที่:

• ความยาว = A + B
• มี 'a' จำนวน A ตัว และ 'b' จำนวน B ตัว
• ไม่มี substring "aaa" หรือ "bbb"

ตัวอย่าง: A=4, B=1 → "aabaa"

วิธีแก้ปัญหา (Greedy)

1. ตัวอักษรที่มากกว่า ให้วาง 2 ตัวติดกัน แล้วตามด้วยอีกตัวหนึ่งตัว (ถ้ายังเหลือ)
2. ทำซ้ำจนความต่างน้อยกว่า 2
3. สลับกันวางตัวอักษรที่เหลือ

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

#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 += "aa";
                A -= 2;
                if(B > 0) { ret += 'b'; B--; }
            } else {
                ret += "bb";
                B -= 2;
                if(A > 0) { ret += 'a'; A--; }
            }
        }
        
        while(A > 0 || B > 0) {
            if(A > 0 && (ret.size() < 2 || 
               !(ret[ret.size()-1] == 'a' && ret[ret.size()-2] == 'a'))) {
                ret += 'a'; A--;
                if(B > 0) { ret += 'b'; B--; }
            } else {
                ret += 'b'; B--;
                if(A > 0) { ret += 'a'; A--; }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.strWithout3a3b(4, 1);
    return 0;
}

อินพุต

4 1

เอาต์พุต

"aabaa"