Cho hai số nguyên A và B, trả về chuỗi S thỏa mãn:
Độ dài A+B, chứa đúng A chữ 'a' và B chữ 'b'
Không chứa substring "aaa" hay "bbb"
Ví dụ: A=4, B=1 → "aabaa".
Giải pháp tham lam:
While |A-B| ≥ 2:
Nếu A > B: thêm "aa", A-=2; nếu B>0 thêm "b", B--
Ngược lại: thêm "bb", B-=2; nếu A>0 thêm "a", A--While A>0 hoặc B>0:
Thêm ký tự còn nhiều hơn, đảm bảo không tạo ra 3 ký tự liên tiếp giống nhau
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; } }; int main(){ Solution ob; cout << (ob.strWithout3a3b(4, 1)); }Đầu vào
4 1
Đầu ra
"aabaa"