1202. Smallest String With Swaps

Problem

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the 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"

Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

Problem Summary

Given a string s, and an array pairs of some "index pairs" in the string, where pairs[i] = [a, b] represents two indices in the string (0-indexed). You can swap the characters at any pair of indices in pairs any number of times. Return the lexicographically smallest string that s can become after several swaps.

Note:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s contains only lowercase English letters

Solution Approach

• Given a string and indices in the string that can be swapped. The task is to obtain the lexicographically smallest string after swaps.
• This problem can be solved with Union Find. First Union() all swappable indices. Within each set, sort in ascending lexicographical order. Finally, scan the original string from left to right, and for each position, find the smallest character in its corresponding set to replace it. After each replacement, remove that character from the set (to prevent it from being used again). The final string obtained is the lexicographically smallest string.

Code

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

func smallestStringWithSwaps(s string, pairs [][]int) string {
	uf, res, sMap := template.UnionFind{}, []byte(s), map[int][]byte{}
	uf.Init(len(s))
	for _, pair := range pairs {
		uf.Union(pair[0], pair[1])
	}
	for i := 0; i < len(s); i++ {
		r := uf.Find(i)
		sMap[r] = append(sMap[r], s[i])
	}
	for _, v := range sMap {
		sort.Slice(v, func(i, j int) bool {
			return v[i] < v[j]
		})
	}
	for i := 0; i < len(s); i++ {
		r := uf.Find(i)
		bytes := sMap[r]
		res[i] = bytes[0]
		sMap[r] = bytes[1:len(bytes)]
	}
	return string(res)
}