Smallest String With Swaps
MediumStringMathSorting
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:
defbcaExplanation:
Two connected components: {0,1,2} and {3,4}. In component {0,1,2}, characters 'f','e','d' sort to 'd','e','f'. In component {3,4}, characters 'c','b' sort to 'b','c'. 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⁵