Smallest String With Swaps
Medium · union find
You are given a string s of lowercase letters and a list pairs of index pairs [a, b]. For any pair in the list, you may swap the letters at positions a and b. You can use any pair as many times as you like, in any order.
Return the alphabetically smallest string you can make. (Compare strings from the left: the string with the smaller letter at the first position where they differ is the smaller one.)
Examples
Example 1
Input: s = "dcab", pairs = [[0, 3], [1, 2]]
Output: "bacd"
Positions 0 and 3 can trade letters d and b, and positions 1 and 2 can trade c and a. Putting the smaller letter first in each pair gives bacd.
Example 2
Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]]
Output: "abcd"
The extra pair links the two groups, so all four letters can be arranged freely.
Example 3
Input: s = "cba", pairs = []
Output: "cba"
With no swaps allowed, the string stays as it is.
Constraints
- 1 <= len(s) <= 1000
- 0 <= len(pairs) <= 1000
- s has only lowercase letters.
- Each pair holds two positions in the range 0 to len(s) - 1. The two positions of a pair may be equal, and a pair may appear more than once.