We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest String With Swaps

Difficulty: Medium

Problem Description

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices (0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps.

Key Insights

  • The problem can be visualized as a graph where each index in the string represents a node.
  • An edge exists between two nodes if their corresponding indices can be swapped.
  • The connected components of this graph determine which characters can be rearranged among themselves.
  • Sorting the characters within each connected component will help in obtaining the lexicographically smallest string.

Space and Time Complexity

Time Complexity: O(N log N + M), where N is the length of the string and M is the number of pairs. Sorting the characters takes O(N log N) and traversing pairs takes O(M).

Space Complexity: O(N + M), where N is for storing the graph and M for the Union-Find structure.

Solution

The solution employs a Union-Find (Disjoint Set Union) data structure to group indices that can be swapped. First, we create a graph based on the provided pairs, then determine the connected components. For each component, we collect the characters, sort them, and place them back into their original indices in sorted order to form the final string.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        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 the indices based on pairs
    for a, b in pairs:
        uf.union(a, b)

    # Group characters by their root
    from collections import defaultdict
    components = defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        components[root].append(i)

    # Create the smallest string
    s_list = list(s)
    for indices in components.values():
        # Extract characters, sort them
        chars = sorted(s_list[i] for i in indices)
        # Place them back in sorted order
        for i, char in zip(sorted(indices), chars):
            s_list[i] = char

    return ''.join(s_list)
← Back to All Questions