Problem Description

Given a string s and an array of pairs pairs where each pair [a, b] indicates that you can swap the characters at indices a and b in s as many times as you like, return the lexicographically smallest string that can be obtained after any number of swaps.

• Each pair allows you to swap the two specified indices as often as you want.
• You may perform swaps in any order and as many times as needed.
• All indices are zero-based.
• There is one unique solution for the given input.

Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= a, b < s.length
• s consists of lowercase English letters.

Thought Process

When first approaching this problem, you might think about simulating all possible swaps, trying every combination until the smallest string is found. However, this quickly becomes infeasible as the number of swaps and string length grows.

Instead, notice that the swap pairs define groups of indices that can be freely swapped among themselves. If two indices are connected (directly or indirectly) via the swap pairs, their characters can be rearranged in any order within that group.

The key insight is to identify these groups (connected components), and for each group, sort the characters and assign them to the sorted indices to get the smallest possible string.

This reduces the problem from simulating swaps to a problem about finding connected components and sorting.

Solution Approach

To solve the problem efficiently, follow these steps:

1. Model the Problem as a Graph:
   • Each index in the string is a node.
   • Each pair in pairs is an undirected edge between two nodes.
   • All indices connected via swaps form a connected component.
2. Find Connected Components:
   • Use Union-Find (Disjoint Set Union) or DFS/BFS to group indices that can be swapped among each other.
3. Sort Characters Within Each Component:
   • For each group of indices, collect the corresponding characters from s.
   • Sort both the indices and the characters.
   • Assign the smallest characters to the smallest indices, the next smallest to the next index, and so on.
4. Reconstruct the Result:
   • Build a new string by placing the sorted characters at the correct positions.

We use Union-Find because it efficiently merges sets and finds the root of each component in nearly constant time, which is essential given the large constraints.

Example Walkthrough

Example Input:
s = "dcab"
pairs = [[0,3],[1,2]]

1. Build the Graph:
   • Pair [0,3]: connect indices 0 and 3
   • Pair [1,2]: connect indices 1 and 2
   • Connected components: {0,3}, {1,2}
2. Group Indices:
   • First group: indices [0,3] (chars: 'd', 'b')
   • Second group: indices [1,2] (chars: 'c', 'a')
3. Sort and Assign:
   • First group: indices [0,3], chars sorted: ['b', 'd'] → assign 'b' to 0, 'd' to 3
   • Second group: indices [1,2], chars sorted: ['a', 'c'] → assign 'a' to 1, 'c' to 2
4. Result:
   • New string: "bacd"

This is the lexicographically smallest string obtainable with the allowed swaps.

Time and Space Complexity

• Brute-force Approach:
  • Would involve generating all permutations via allowed swaps — exponential time, not feasible.
• Optimized Approach (Union-Find):
  • Time Complexity:
    • Union-Find operations: O(N + P * α(N)), where N = length of s, P = number of pairs, and α is the inverse Ackermann function (almost constant).
    • Grouping and sorting: O(N log N) (in the worst case, all indices are in one group and need sorting).
    • Total: O(N log N)
  • Space Complexity:
    • O(N) for the Union-Find structure and groupings.

Summary

The problem is elegantly solved by recognizing that swap pairs define groups of indices whose characters can be freely permuted. By using Union-Find to efficiently group these indices, and then sorting and reassigning their characters, we can construct the smallest possible string in optimal time. This approach leverages classic graph and sorting techniques, making the solution both efficient and conceptually clean.

Code Implementation

class Solution:
    def smallestStringWithSwaps(self, s, pairs):
        parent = [i for i in range(len(s))]

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

        def union(x, y):
            parent[find(x)] = find(y)

        for a, b in pairs:
            union(a, b)

        from collections import defaultdict
        groups = defaultdict(list)
        for i in range(len(s)):
            root = find(i)
            groups[root].append(i)

        res = list(s)
        for indices in groups.values():
            chars = [s[i] for i in indices]
            indices.sort()
            chars.sort()
            for idx, ch in zip(indices, chars):
                res[idx] = ch
        return ''.join(res)
      

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        };

        for (auto& p : pairs) {
            int a = p[0], b = p[1];
            parent[find(a)] = find(b);
        }

        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[find(i)].push_back(i);

        string res = s;
        for (auto& kv : groups) {
            vector<int>& indices = kv.second;
            vector<char> chars;
            for (int idx : indices) chars.push_back(s[idx]);
            sort(indices.begin(), indices.end());
            sort(chars.begin(), chars.end());
            for (int i = 0; i < indices.size(); ++i)
                res[indices[i]] = chars[i];
        }
        return res;
    }
};
      

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        int[] parent = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;

        // Find with path compression
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        // Union
        void union(int x, int y) {
            parent[find(x)] = find(y);
        }

        for (List<Integer> p : pairs) {
            union(p.get(0), p.get(1));
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }

        char[] res = s.toCharArray();
        for (List<Integer> indices : groups.values()) {
            List<Character> chars = new ArrayList<>();
            for (int idx : indices) chars.add(s.charAt(idx));
            Collections.sort(indices);
            Collections.sort(chars);
            for (int i = 0; i < indices.size(); ++i)
                res[indices.get(i)] = chars.get(i);
        }
        return new String(res);
    }
}
      

var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const parent = Array.from({length: n}, (_, i) => i);

    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }

    function union(x, y) {
        parent[find(x)] = find(y);
    }

    for (const [a, b] of pairs) {
        union(a, b);
    }

    const groups = {};
    for (let i = 0; i < n; ++i) {
        const root = find(i);
        if (!(root in groups)) groups[root] = [];
        groups[root].push(i);
    }

    const res = s.split('');
    for (const indices of Object.values(groups)) {
        const chars = indices.map(i => s[i]);
        indices.sort((a, b) => a - b);
        chars.sort();
        for (let i = 0; i < indices.length; ++i) {
            res[indices[i]] = chars[i];
        }
    }
    return res.join('');
};