Hợp nhất lớn nhất của 2 chuỗi trong C++

Cho 2 chuỗi a, b và chuỗi merge. Lấy ký tự từ a, b để merge sao cho kết quả lớn nhất theo thứ tự từ điển (lexicographically).

Quy tắc

• Nếu a không rỗng → lấy ký tự đầu a vào merge
• Nếu b không rỗng → lấy ký tự đầu b vào merge
• Nếu cả 2 không rỗng → lấy từ chuỗi lớn hơn theo từ điển trước

Ví dụ

a="bacaa", b="abcaa"

Output: "babcacaaaa"

Vì 'b' > 'a' → lấy từ a trước.

Cách tiếp cận: Đệ quy

• Hàm concatenateLargest(a, b)
• Nếu a hoặc b rỗng → trả về a+b
• Nếu a <= b → lấy b[0] + concatenateLargest(a, b.substr(1))
• Ngược lại → lấy a[0] + concatenateLargest(a.substr(1), b)

Code C++

#include <bits/stdc++.h>
using namespace std;

string concatenateLargest(string a, string b) {
    if (a.empty() || b.empty()) return a + b;
    if (a <= b) return b[0] + concatenateLargest(a, b.substr(1));
    else return a[0] + concatenateLargest(a.substr(1), b);
}

int main() {
    string a = "bacaa", b = "abcaa";
    cout << concatenateLargest(a, b) << endl;
    return 0;
}

Kết quả

bacabcaaaa

Kết quả merge theo quy tắc lexicographically largest.