Largest Merge ของสตริง 2 ตัวใน C++

โจทย์

กำหนด 2 สตริง a, b สร้างสตริง merge โดยทุกขั้นตอนเลือกตัวแรกของ a หรือ b ที่ Lexicographically larger (มากกว่าตามพจนานุกรม) ต่อท้าย merge จนกว่าทั้งคู่ว่าง

ตัวอย่าง

a = "bacaa", b = "abcaa"

เปรียบเทียบ "bacaa" vs "abcaa" → 'b' > 'a' เลือก 'b' จาก a

เหลือ a="acaa", b="abcaa" → 'a'='a' ต้องดูต่อ → "acaa" > "abcaa" เลือก 'a' จาก a

... ผลลัพธ์: "bacabcaaaa"

แนวคิด: Greedy + String Comparison

ทุกขั้นตอนเปรียบเทียบสตริงที่เหลือทั้งคู่ a และ b เลือกตัวแรกของสตริงที่ "มากกว่า"

โค้ด C++ (Recursive)

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

string largestMerge(string a, string b) {
    if (a.empty()) return b;
    if (b.empty()) return a;
    
    if (a > b) { // Lexicographical comparison
        return a[0] + largestMerge(a.substr(1), b);
    } else {
        return b[0] + largestMerge(a, b.substr(1));
    }
}

int main() {
    string a = "bacaa";
    string b = "abcaa";
    cout << largestMerge(a, b) << endl; // bacabcaaaa
    
    // Test cases
    cout << largestMerge("abc", "def") << endl;     // defabc
    cout << largestMerge("aaa", "aaa") << endl;     // aaaaaa
    cout << largestMerge("z", "a") << endl;         // za
    cout << largestMerge("", "hello") << endl;      // hello
    
    return 0;
}

Iterative Version (มีประสิทธิภาพมากกว่า)

string largestMergeIterative(string a, string b) {
    string result;
    result.reserve(a.size() + b.size());
    
    while (!a.empty() && !b.empty()) {
        if (a > b) {
            result += a[0];
            a = a.substr(1);
        } else {
            result += b[0];
            b = b.substr(1);
        }
    }
    result += a + b; // ต่อส่วนที่เหลือ
    return result;
}

// Optimized: ใช้ index แทน substr (O(1) per step)
string largestMergeOpt(string a, string b) {
    string result;
    result.reserve(a.size() + b.size());
    size_t i = 0, j = 0;
    
    while (i < a.size() && j < b.size()) {
        if (a.compare(i, string::npos, b, j, string::npos) >= 0) {
            result += a[i++];
        } else {
            result += b[j++];
        }
    }
    result.append(a, i, string::npos);
    result.append(b, j, string::npos);
    return result;
}

Complexity

หมายเหตุ: String comparison worst-case O(n) ทำให้ Overall O(n²) - ไม่มีวิธี O(n) แบบง่าย เพราะต้องเปรียบเทียบ Suffix

ผลลัพธ์

bacabcaaaa
defabc
aaaaaa
za
hello

สรุป

Largest Merge = Greedy เลือกตัวแรกของสตริงที่ Lexicographically Larger ใช้ string::compare กับ index เพื่อประสิทธิภาพ ดูเป็น LeetCode 1754