Given a string and index pairs that can be swapped any number of times, return the lexicographically smallest string obtainable. DSU path compression helps group indices into connected swap components quickly.
s = input string, pairs = swappable index pairs
lexicographically smallest string
Example 1:
Input:
s = "dcab" pairs = [[0,3],[1,2]]
Output:
bacd
Explanation:
Indices {0,3} and {1,2} form two components, allowing the smallest arrangement bacd.
Example 2:
Input:
s = "cba" pairs = [[0,1],[1,2]]
Output:
abc
Explanation:
All indices are connected, so the whole string can be sorted.
Example 3:
Input:
s = "abc" pairs = []
Output:
abc
Explanation:
With no swaps, the string remains unchanged.