Tách chuỗi nối trong C++

Giới thiệu

Cho danh sách chuỗi. Nối chúng thành vòng (loop), mỗi chuỗi có thể đảo ngược hoặc không. Sau đó cắt vòng tại 1 điểm bất kỳ để thành chuỗi thẳng. Tìm chuỗi lớn nhất theo thứ tự từ điển (lexicographically largest).

Thuật toán

1. Đối với mỗi chuỗi, chọn hướng (gốc hoặc đảo) cho chuỗi lớn nhất từ điển. (Vì trong vòng, ta có thể cắt ở bất kỳ đâu, nên mỗi chuỗi nên lấy dạng lớn nhất).
2. Với mỗi chuỗi i và mỗi hướng (gốc/đảo), thử cắt tại mọi vị trí k trong chuỗi đó: kết quả = s[i][k:] + s[i+1..] + s[0..i-1] + s[i][:k].
3. Lấy max của tất cả.

Cài đặt C++

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

class Solution {
    string best;
    void tryCut(int idx, vector& strs, bool rev) {
        string cur = strs[idx];
        if (rev) reverse(cur.begin(), cur.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 < cur.size(); k++) {
            string cand = cur.substr(k) + after + before + cur.substr(0, k);
            if (cand > best) best = cand;
        }
    }
public:
    string splitLoopedString(vector& strs) {
        // Bước 1: chuẩn hóa mỗi chuỗi thành dạng lớn nhất
        for (auto& s : strs) {
            string rev = s;
            reverse(rev.begin(), rev.end());
            if (rev > s) s = rev;
        }
        best = "";
        for (int i = 0; i < strs.size(); i++) {
            tryCut(i, strs, false);
            tryCut(i, strs, true);
        }
        return best;
    }
};

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

Giải thích ví dụ

Chuỗi: "abc", "xyz". Chuẩn hóa: "cba", "zyx". Vòng: cba + zyx. Cắt tại 'a' giữa cba → "zyx" + "cb" + "a" = "zyxcba" (lớn nhất).

Độ phức tạp

• Thời gian: O(N * L²) với N = số chuỗi, L = độ dài trung bình.
• Không gian: O(L) cho chuỗi tạm.

LeetCode 555 "Split Concatenated Strings".