Domain 2MediumMEDIUM

Smallest String With Swaps

Identify connected components using Union-Find, then sort characters within each component and place them at the sorted indices to achieve lexicographically smallest string.

Domain: medium•Updated: 2026-09-10
#Union-Find#DSU#O(N log N)#O(N)

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 swap s[a] and s[b].

Outputs:

  • The lexicographically smallest resulting string.

Implicit Constraints & Logic:

  1. 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).
  2. Independence of Components: Indices not linked by pairs cannot interact with each other. We must solve for each connected group independently and combine results.
  3. 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:

  • pairs is empty: No swaps allowed; return original s.
  • 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 (N!N!). Even a BFS/DFS on states is too slow for 10510^5.

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:

  1. Identify all groups of indices using Union-Find.
  2. For each group, collect the characters currently at those indices and sort them alphabetically.
  3. Sort the indices belonging to that group numerically (ascending).
  4. 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

  1. Initialize Union-Find: Create a parent array where each element is initially its own parent (representing NN disjoint sets). Implement iterative find() with path compression for efficiency to avoid recursion depth issues in Python.
  2. Build Components: Iterate through every pair in pairs. Perform the union operation on their roots to merge components.
  3. Group Data: After processing all pairs, iterate over indices 0…N−10 \dots N-1. 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.
  4. 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.
  5. Return: Join the result list into a string.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N+M⋅α(N))O(N \log N + M \cdot \alpha(N)), where NN is s.length, MM is pairs.length.
    • Union-Find operations take nearly constant time α(N)\alpha(N). Total union cost: O(M⋅α(N))O(M \cdot \alpha(N)).
    • Grouping characters takes O(N)O(N).
    • Sorting characters within groups sums to O(Nlog⁡N)O(N \log N) in the worst case (all connected).
  • Space Complexity: O(N)O(N) 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"