Description
Given a string s and pairs of indices, you can swap characters at pairs any number of times. Return the lexicographically smallest string.
Examples
Input:
s = "dcab", pairs = [[0,3],[1,2]]Output:
"bacd"Explanation:
Swap (0,3) and (1,2).
Input:
s = "fedcba", pairs = [[0,1],[1,2],[3,4]]Output:
defcabExplanation:
Two connected components: {0,1,2} and {3,4}. In component {0,1,2}, it is possible to rearrange characters 'f', 'e', 'd' to get 'd', 'e', 'f' in lexicographical order. In component {3,4}, it is possible to rearrange 'b', 'a' to get 'a', 'b'. Position 5 stays unchanged as 'a'.
Input:
s = "xyz", pairs = []Output:
xyzExplanation:
No swaps are allowed, so the string remains unchanged. Each character forms its own component and cannot be moved to any other position.
Constraints
- •
1 ≤ s.length ≤ 10⁵