LeetCode 1202 Smallest String With Swaps - Algorithm

$1.$ Treat indices $0$ to $n-1$ as nodes.

$2.$ Union indices $i$ and $j$ if there is a swap pair [i, j].

$3.$ Group characters by their index's leader.

$4.$ For each group, sort the characters.

$5.$ Rebuild the string: for each position, take the next smallest available character from its group.

Time: $O(n \log n)$ for sorting. DSU part is nearly linear.

Space complexity is $O(n)$ for the data structures used.