Problem Breakdown
We are given a string s and an array of index pairs pairs. Each pair [a, b] allows swapping characters at those positions. We can perform these swaps any number of times. The goal is to return the lexicographically smallest possible string achievable through these operations.
Inputs:
- A lowercase English string
s. - An array of index pairs
pairs, where each pair[a, b]allows us to swaps[a]ands[b].
Outputs:
- The lexicographically smallest resulting string.
Implicit Constraints & Logic:
- Transitivity: If we can swap
(0, 3)and(3, 2), we effectively have a connected component{0, 2, 3}where any character at these indices can move to any other index within that set via swaps (bubble sort logic). - Independence of Components: Indices not linked by
pairscannot interact with each other. We must solve for each connected group independently and combine results. - Greedy Strategy: Within a specific component, we have a fixed set of indices and a fixed multiset of characters currently residing there. To minimize the string lexicographically, we want smaller characters to appear at earlier (smaller) index positions within that component’s range.
Edge Cases:
pairsis empty: No swaps allowed; return originals.- Disconnected indices: Handled naturally by grouping logic.
- Duplicate pairs or cycles in
pairs: Union-Find handles redundant connections efficiently without error.
Intuition
A brute-force approach trying to simulate every swap sequence would be exponential because the number of permutations is huge (). Even a BFS/DFS on states is too slow for .
Key Insight: The problem decomposes into finding Connected Components.
If index i and index j are connected (directly or indirectly), they belong to the same group. Within that group, we can rearrange characters arbitrarily. To make the string smallest:
- Identify all groups of indices using Union-Find.
- For each group, collect the characters currently at those indices and sort them alphabetically.
- Sort the indices belonging to that group numerically (ascending).
- Place the sorted characters into the sorted index positions for that specific component.
This greedy placement ensures s[0] gets the smallest available character from its reachable set, then s[next_index_in_group], and so on.
Approach
- Initialize Union-Find: Create a parent array where each element is initially its own parent (representing disjoint sets). Implement iterative
find()with path compression for efficiency to avoid recursion depth issues in Python. - Build Components: Iterate through every pair in
pairs. Perform the union operation on their roots to merge components. - Group Data: After processing all pairs, iterate over indices . For each index, find its root parent and append
(index, character)into a dictionary keyed by that root. This groups characters with their original positions for every component. - Reconstruct String:
- Initialize an output list of size
N. - Iterate through the values in our grouping dictionary (each value is a list of tuples).
- For each group, extract indices and sort them to get target order. Extract characters and sort them alphabetically.
- Zip sorted chars with sorted indices and assign back to the output list.
- Initialize an output list of size
- Return: Join the result list into a string.
Complexity Analysis
- Time Complexity: , where is
s.length, ispairs.length.- Union-Find operations take nearly constant time . Total union cost: .
- Grouping characters takes .
- Sorting characters within groups sums to in the worst case (all connected).
- Space Complexity: for the parent array, grouping dictionary, and result list.
Solution
from collections import defaultdict
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: list[list[int]]) -> str:
n = len(s)
# Initialize Union-Find parent array
parent = list(range(n))
# Iterative find with path compression to avoid recursion depth issues
def find(i):
root = i
while parent[root] != root:
root = parent[root]
# Path compression
curr = i
while curr != root:
next_node = parent[curr]
parent[curr] = root
curr = next_node
return root
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
# Union by arbitrary linking (rank optimization optional but simple linking works with path compression for amortized efficiency)
parent[root_i] = root_j
# Process all pairs to build connected components
for a, b in pairs:
union(a, b)
# Group characters by their component's representative (root)
groups = defaultdict(list)
for i, char in enumerate(s):
root = find(i)
groups[root].append((i, char))
result = list(s)
# For each connected group: sort chars and indices to place smallest at earliest index
for idx_list in groups.values():
sorted_indices = [idx for idx, _ in idx_list]
sorted_chars = sorted([char for _, char in idx_list])
# Assign sorted characters back to the original positions of this group
for i, new_char in zip(sorted_indices, sorted_chars):
result[i] = new_char
return "".join(result)
# Example usage (uncommenting these lines allows local testing if needed)
# sol = Solution()
# print(sol.smallestStringWithSwaps("dcab", [[0,3],[1,2]])) # Output: "bacd"