hardGraphsPure DSA~35 min
Lexicographically Smallest String After Allowed Swaps
Certain index pairs of a string may be swapped any number of times. Using those swaps freely, produce the lexicographically smallest possible string.
Problem
Given a string s and a list pairs of index pairs [a, b] (0-indexed) that may be swapped any number of times, return the lexicographically smallest string obtainable. Swaps are transitive: any indices connected through pairs can be freely rearranged among themselves.
Input
A string s and a list pairs of [a, b] swappable index pairs.
Output
The lexicographically smallest reachable string.
Constraints
- 1 <= s.length <= 10^5
- 0 <= pairs.length <= 10^5
- s contains only lowercase letters.
Examples
Example 1
Input
s = "dcab", pairs = [[0,3],[1,2]]
Output
"bacd"
Swap indices {0,3} and {1,2} independently to sort each group.
Example 2
Input
s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output
"abcd"
Indices 0,1,2,3 form one group, so the whole string sorts.