1202. Smallest String With Swaps

https://leetcode.com/problems/smallest-string-with-swaps/

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.

---

Intuition

Discover connected components - use union find

Build a list of sorted characters at each index

If index is not part of larger connected component sorted list is just that character

Use priority queue to build the sorted list of chars

Save priority queue against root of each index

Traverse string, find root, and append the char at top of priority queue

---

Time - O(N log N)

Space - O(N)

---

	class Solution {
	int[] parent;
	public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
	parent = new int[s.length()];
	for (int i = 0; i < parent.length; i++) {
	parent[i] = i;
	}
	// detect connected components
	for (List<Integer> pair: pairs) {
	union(pair.get(0), pair.get(1));
	}
	// Sort characters of connected component at each position
	Map<Integer, PriorityQueue<Character>> map = new HashMap<Integer, PriorityQueue<Character>>();
	for (int i = 0; i < s.length(); i++) {
	int root = find(i);
	// Build a sorted list of characters from connection component at each position
	map.putIfAbsent(root, new PriorityQueue<Character>());
	map.get(root).offer(s.charAt(i));
	}
	StringBuilder sb = new StringBuilder();
	// Build the answer with smallest char at each position
	for (int i = 0; i < s.length(); i++) {
	sb.append(map.get(parent[i]).poll());
	}
	return sb.toString();
	}
	private int find(int a) {
	while (parent[a] != a) {
	parent[a] = parent[parent[a]];
	a = parent[a];
	}
	return a;
	}
	private void union(int a, int b) {
	int parentA = find(a);
	int parentB = find(b);
	if (parentA < parentB) {
	parent[parentB] = parentA;
	} else {
	parent[parentA] = parentB;
	}
	}
	}

view raw 1202.SmallestStringWithSwaps.java hosted with ❤ by GitHub