สตริงเล็กที่สุดนิยามลีกซิโคกราฟิกด้วยการสป (Smallest String With Swaps) ใน C++

ให้ String s และ Array ของคู่ Index pairs โดย pairs[i] = [a, b] หมายถึงเราสามารถ **สลับตัวอักษรตำแหน่ง a และ b ได้ไม่จำกัดครั้ง** (โดยตรงหรือโดยอ้อมผ่าน Chain ของ Pairs)

เป้าหมาย: หา String ที่ **เล็กที่สุดนิยาม Lexicographically** ที่ได้จากการสปตาม Pairs ที่อนุญาต

ตัวอย่าง

s = "dcab", pairs = [[0,3], [1,2]]

1. สป (0,3): "dcab" -> "bcad"
2. สป (1,2): "bcad" -> "bacd"

คำตอบ: "bacd"

แนวคิดหลัก: Union-Find (Disjoint Set Union - DSU)

Pairs สร้าง **Connected Components** ขึ้นมา ภายใน Component เดียวกัน สลับตัวอักษรได้ทุกคู่ -> **จัดเรียงตัวอักษรใน Component ให้เล็กที่สุดได้**

1. สร้าง DSU หา Parent ของแต่ละ Index
2. จัดกลุ่ม Character ตาม Root Parent
3. Sort ตัวอักษรในแต่ละกลุ่ม **จากมากไปน้อย (Descending)** เพื่อ Pop_back ได้ O(1)
4. สร้างผลลัพธ์: แต่ละตำแหน่ง i เอา Char ตัวสุดท้ายของกลุ่ม Parent[i]

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

class Solution {
public:
    vector<int> parent;

    int getParent(int x) {
        if (parent[x] == -1) return x;
        return parent[x] = getParent(parent[x]); // Path Compression
    }

    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        parent = vector<int>(n, -1);
        string ret(n, '*');

        // 1. Union-Find: Group indices
        for (auto& p : pairs) {
            int u = p[0], v = p[1];
            int pu = getParent(u), pv = getParent(v);
            if (pu != pv) parent[pu] = pv;
        }

        // 2. Collect chars per component
        vector<char> buckets[n];
        for (int i = 0; i < n; i++) {
            buckets[getParent(i)].push_back(s[i]);
        }

        // 3. Sort each bucket descending (for O(1) pop_back)
        for (int i = 0; i < n; i++) {
            sort(buckets[i].rbegin(), buckets[i].rend());
        }

        // 4. Build result
        for (int i = 0; i < n; i++) {
            ret[i] = buckets[getParent(i)].back();
            buckets[getParent(i)].pop_back();
        }
        return ret;
    }
};

Input / Output

Input:  "dcab" [[0,3],[1,2]]
Output: "bacd"

ความซับซ้อน (Complexity)

• Time: O(N α(N) + N log N) ≈ O(N log N) — DSU + Sorting
• Space: O(N) — Parent array + Buckets

หัวใจสำคัญคือ **Connected Components = สลับได้หมดในกลุ่ม** -> เรียงตัวอักษรในกลุ่มให้เล็กสุดครับ