Minimize a String Using Allowed Swaps

You are given a string s of lowercase English letters and an array pairs, where each element pairs[i] = [a, b] means you may swap the characters at indices a and b. You may perform any number of swaps, and each allowed pair may be used multiple times.

Return the lexicographically smallest string that can be obtained.

Indices are zero-based.

Example 1:

Input: s = "dcab", pairs = [[0, 3], [1, 2]]
Output: "bacd"

Example 2:

Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]]
Output: "abcd"

Constraints:

• 1 <= s.length <= 100000
• 0 <= pairs.length <= 100000
• pairs[i].length == 2
• 0 <= pairs[i][0], pairs[i][1] < s.length

Minimize a String Using Allowed Swaps

Hints

1. Think of the indices as nodes in a graph. If two indices are connected directly or indirectly through allowed pairs, their characters can be rearranged among those indices.
2. For each connected component, collect its indices and characters. Sort the indices and sort the characters, then place the smallest characters into the smallest indices.