Lexicographically Smallest Equivalent String ใน C++

ปัญหา

ให้ String A, B ความยาวเท่ากัน A[i] เทียบเท่า B[i] ความสัมพันธ์ Equivalence (Reflexive, Symmetric, Transitive)

ให้ String S หา Equivalent String ที่เล็กที่สุด Lexicographically

ตัวอย่าง

A="parker", B="morris", S="parser"

Equivalence Groups: [m,p], [a,o], [k,r,s], [e,i]

ตัวแทนเล็กสุดของแต่ละกลุ่ม: m, a, k, e

S="parser" → "makkek"

อัลกอริทึม: Union-Find (Disjoint Set Union)

1. สร้าง DSU 26 ตัว (a-z)
2. Union(A[i], B[i]) ทุก i
3. Find Parent ของแต่ละตัวอักษรใน S ใช้ตัวแทน (Root) ที่เล็กที่สุด

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

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

class Solution {
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] == -1) return x;
        return parent[x] = find(parent[x]); // Path Compression
    }
    
    void unite(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return;
        // Root ที่เล็กกว่าเป็น Parent
        if (pa < pb) parent[pb] = pa;
        else parent[pa] = pb;
    }
    
public:
    string smallestEquivalentString(string A, string B, string S) {
        parent.assign(26, -1);
        for (int i = 0; i < A.size(); i++)
            unite(A[i] - 'a', B[i] - 'a');
        
        string result;
        for (char c : S)
            result += char('a' + find(c - 'a'));
        return result;
    }
};

int main() {
    Solution ob;
    cout << ob.smallestEquivalentString("parker", "morris", "parser") << endl; // makkek
    return 0;
}

ผลลัพธ์

makkek

Complexity

• Time: O(N α(26)) ≈ O(N) โดย α = Inverse Ackermann
• Space: O(1) - Fixed 26 Elements