LeetCode Solutions Blog

Smallest String With Swaps

Number: 1308

Difficulty: Medium

Paid? No

Companies: Uber, PhonePe

Problem Description

Given a string s and a list of index pairs, each pair indicates two indices in s that can be swapped any number of times. The goal is to return the lexicographically smallest string possible by performing any series of swaps allowed by the given pairs.

Key Insights

The index pairs form connections that can be modeled as a graph. Any indices that are connected (directly or indirectly) form a component in which characters can be arbitrarily rearranged.
By finding all connected components, we can independently sort the characters from those indices and place them back in sorted order to achieve the smallest possible overall string.
Approaches like Union Find, Depth-First Search, or Breadth-First Search can be used to identify these connected components.

Space and Time Complexity

Time Complexity: O(n log n + m * α(n))
Space Complexity: O(n)

Solution

The solution uses the Union Find (Disjoint Set Union) data structure:

Use the union find structure to connect indices from the given pairs.
Traverse through all indices and group them by their root parent (i.e., the connected component they belong to).
For each group, extract the characters, sort them, and then reassign the sorted characters back to their corresponding positions in the string.
Finally, join the characters to form the lexicographically smallest string possible.

Code Solutions

# Python code solution for Smallest String With Swaps

class UnionFind:
    def __init__(self, n):
        # Initialize parent list; each index is its own parent initially
        self.parent = list(range(n))
    
    def find(self, x):
        # Path compression optimization
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union the sets that x and y belong to
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def smallestStringWithSwaps(s, pairs):
    n = len(s)
    uf = UnionFind(n)
    
    # Union all pairs
    for x, y in pairs:
        uf.union(x, y)
    
    from collections import defaultdict
    groups = defaultdict(list)
    
    # Group indices by their root parent
    for idx in range(n):
        root = uf.find(idx)
        groups[root].append(idx)
    
    s_list = list(s)
    
    # For each group, sort the indices and the corresponding characters,
    # then assign the smallest characters to the smallest indices.
    for indices in groups.values():
        # Extract the characters from the current group
        chars = [s_list[i] for i in indices]
        indices.sort()
        chars.sort()
        for i, char in zip(indices, chars):
            s_list[i] = char
    
    return "".join(s_list)

# Example usage:
# s = "dcab"
# pairs = [[0,3],[1,2]]
# print(smallestStringWithSwaps(s, pairs))  # Output: "bacd"