Medium · DSU Component Sorting
Understand → Visualise → Practice.
Indices joined by swap pairs may exchange characters repeatedly. Return the lexicographically smallest reachable string.
Swaps along connected index pairs can arrange that group's characters in any order. So group indices with union-find, sort each group's characters, and place them back in index order.
Each pair joins two index sets.
Gather the characters of each group (the indices are visited in increasing order).
Give each group's indices its characters in ascending order.
O(n log n + p α(n)) time and O(n) space.
Swapping greedily pair by pair can't reach orders that need several swaps through intermediate indices.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.