#1202
Smallest String With Swaps
specialist · 705 · lc medium +30 · verified · 60.4% accepted · 3,901 likes · top 59%
Description
You are given a string s and a list of index pairs pairs, where pairs[i] = [a, b] indicates two 0-indexed positions in s. You may swap characters between any listed pair of positions as many times as you wish.
Return the lexicographically smallest version of s achievable through these swaps.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"
Code
1
2
3