algoadvance

Given a string s, no longer than 4,000 characters, and a list pairs of pairs of indices in the string (0-indexed), determine the lexicographically smallest string that can be obtained by swapping the characters at the indices in the given pairs any number of times.

Clarifying Questions

1. Are there any constraints on the pairs?
   • Pairs may indicate any valid indices in the string, and they could contain duplicate pairs or indices.
2. Can swaps be done transitively?
   • Yes, if index i can be swapped with j, and j with k, then effectively i can be swapped with k.
3. What should we return if no swaps are possible?
   • Return the original string as it is already the smallest possible.
4. Are pairs bidirectional?
   • Yes, if (i, j) is in pairs, you can swap both i with j and j with i.

Strategy

1. Union-Find Data Structure: We’ll use the Union-Find data structure to group all indices that can be swapped with each other. Each group represents indices that are inter-swappable.
2. Sorting Groups: Once we have groups, we’ll extract the characters corresponding to these groups, sort them and place them back in the original indices to get the lexicographically smallest string.

Code

class UnionFind:
    def __init__(self, size):
        self.root = list(range(size))
        self.rank = [1] * size

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

def smallestStringWithSwaps(s, pairs):
    n = len(s)
    union_find = UnionFind(n)
    
    for x, y in pairs:
        union_find.union(x, y)

    root_to_component = {}
    for i in range(n):
        root = union_find.find(i)
        if root not in root_to_component:
            root_to_component[root] = []
        root_to_component[root].append(i)

    smallest_string = list(s)
    for component in root_to_component.values():
        chars = [s[i] for i in component]
        chars.sort()
        for i, char in zip(sorted(component), chars):
            smallest_string[i] = char

    return ''.join(smallest_string)

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

Time Complexity

• Union-Find Operations: Union and find operations take O(α(N)) time, where α is the inverse Ackermann function, which is very small (almost constant time). Hence, for N operations, it’s effectively O(N).
• Sorting Groups: Sorting the characters in each connected component will take O(N log N), where N is the length of the string.

Overall, the time complexity is O(N log N) due to the sorting operation.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?