Introduction

In this blog post, we will explore how to solve the LeetCode problem "1202" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2: Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3: Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc" Constraints: 1 <= s.length <= 10^5 0 <= pairs.length <= 10^5 0 <= pairs[i][0], pairs[i][1] < s.length s only contains lower case English letters.

Explanation

Here's a solution to the problem, focusing on efficiency and clarity:

• Identify Connected Components: The core idea is to use Disjoint Set Union (DSU) to find connected components within the string indices based on the pairs. Each connected component represents a group of indices whose characters can be freely swapped.
• Sort Within Components: For each connected component, extract the characters and their indices. Sort both the characters and indices. Then, place the smallest character at the smallest index, the second smallest character at the second smallest index, and so on. This guarantees the lexicographically smallest string for that component.

• Reconstruct String: Combine the modified characters from all components back into a single string.

• Runtime Complexity: O(N log N) due to sorting the characters and indices within each connected component. In theory DSU can be close to O(1) per operation (amortized), but sorting dominates. Storage Complexity: O(N) for DSU parent array, character lists, and index lists.

Code

    class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y

def smallestStringWithSwaps(s: str, pairs: list[list[int]]) -> str:
    n = len(s)
    dsu = DSU(n)

    # Union connected indices
    for u, v in pairs:
        dsu.union(u, v)

    # Group indices by their connected component (root)
    groups = {}
    for i in range(n):
        root = dsu.find(i)
        if root not in groups:
            groups[root] = []
        groups[root].append(i)

    # For each group, sort the characters and indices
    result = list(s)
    for root, indices in groups.items():
        chars = [s[i] for i in indices]
        indices.sort()
        chars.sort()
        for i, char in enumerate(chars):
            result[indices[i]] = char

    return "".join(result)