Minimize a String Using Allowed Swaps
Company: PayPal
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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`
Quick Answer: This question evaluates understanding of graph connectivity and constrained string reordering, along with proficiency in applying efficient data structures and algorithms for handling large inputs.
You are given a string `s` consisting of lowercase English letters and a list `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 after any sequence of valid swaps.
Indices are zero-based.
Constraints
- 1 <= len(s) <= 100000
- 0 <= len(pairs) <= 100000
- pairs[i].length == 2
- 0 <= pairs[i][0], pairs[i][1] < len(s)
Examples
Input: ('dcab', [[0, 3], [1, 2]])
Expected Output: 'bacd'
Explanation: Indices {0, 3} form one component and {1, 2} form another. Sorting characters within each component gives 'bacd'.
Input: ('dcab', [[0, 3], [1, 2], [0, 2]])
Expected Output: 'abcd'
Explanation: All indices become connected, so the entire string can be rearranged into its lexicographically smallest form.
Hints
- 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.
- 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.