Split Concatenated Strings – หาสตริงมากที่สุดจากการตัด Loop ใน C++

ปัญหา: Split Concatenated Strings

กำหนดรายการสตริง สามารถ กลับด้าน (reverse) แต่ละสตริงได้ แล้วต่อกันเป็น Loop (วงกลม)
หาจุดตัด 1 จุด บน Loop → ได้สตริงปกติ หา สตริงที่มากที่สุด lexicographically

ตัวอย่าง

Input: ["abc", "xyz"]

Loop ตัวเลือก (4 แบบ):

• abcxyz → cut ได้ abcxyz, bcxyza, ..., zabcxy
• abczyx → cut ได้...
• cbaxyz → cut ได้...
• cbazyx → cut ได้ zyxcba (มากที่สุด)

Output: "zyxcba"

แนวทางแก้ปัญหา: Brute Force ทุกความเป็นไปได้

ข้อสังเกต

• แต่ละสตริง เลือก reverse หรือไม่ → 2^n แบบ
• แต่ optimal: แต่ละสตริงควรเลือก orientation ที่มากกว่า (max(s, reverse(s)))
• จากนั้น ลองตัดที่ทุกตำแหน่งในทุกสตริง

ขั้นตอน

1. Preprocess: แต่ละสตริง เลือก max(s, reverse(s))
2. สร้าง Loop string S = s0 + s1 + ... + sn-1
3. สำหรับแต่ละสตริง si (ที่อาจ reverse อีกครั้ง):
   • สร้าง rest = si+1 + ... + sn-1 + s0 + ... + si-1
   • ลองตัดที่ทุกตำแหน่งใน si: si[k:] + rest + si[:k]
   • อัปเดตคำตอบสูงสุด

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

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

class Solution {
    string best = "";

    void tryCut(int idx, const vector<string>& strs, bool rev) {
        string s = strs[idx];
        if (rev) reverse(s.begin(), s.end());

        string before, after;
        for (int i = 0; i < idx; i++) before += strs[i];
        for (int i = idx + 1; i < strs.size(); i++) after += strs[i];

        for (int k = 0; k < s.size(); k++) {
            string candidate = s.substr(k) + after + before + s.substr(0, k);
            if (candidate > best) best = candidate;
        }
    }

    void maximizeStrings(vector<string>& strs) {
        for (auto& s : strs) {
            string rev = s;
            reverse(rev.begin(), rev.end());
            if (rev > s) s = rev;
        }
    }

public:
    string splitLoopedString(vector<string>& strs) {
        maximizeStrings(strs);
        best = "";

        for (int i = 0; i < strs.size(); i++) {
            tryCut(i, strs, false);
            tryCut(i, strs, true);
        }
        return best;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"abc", "xyz"};
    cout << ob.splitLoopedString(v); // zyxcba
    return 0;
}

ความซับซ้อน

• เวลา: O(n × L²) – n = จำนวนสตริง, L = ความยาวรวม (≤ 1000 typical)
• พื้นที่: O(L)

ข้อสังเกต

• LeetCode 555
• Key insight: แต่ละสตริงควรอยู่ใน orientation ที่มากที่สุด (ยกเว้นที่ตัด)
• Brute force ทุกจุดตัดเพราะ L ≤ 1000 → 10⁶ operations OK
• Lexicographic compare ใน C++: string รองรับ > โดยตรง