1202. Smallest String With Swaps


Problem Description

The problem presents us with a string s and a list of pairs, where each pair contains two indices of the string s. We are allowed to swap characters at any of the given pair indices as many times as we wish. The objective is to determine the lexicographically smallest string that can be formed after making any number of swaps among the pairs.

Intuition

To arrive at the solution, we need to think about how the operations will affect the string s. Since any number of swaps can be made, if there is a way to swap between any two indices through a series of swaps, we can effectively consider those characters as part of the same group. This leads us to the concept of "connected components".

A connected component in this context is a set of indices where any index can reach any other index within the same set through the pairs given. Once we've identified these connected components, within each component, we can sort the characters lexicographically and place them back into their original positions. This is possible because swaps within a component can rearrange characters in any order.

To implement this, we use a union-find data structure (also known as the disjoint-set data structure). With union-find, we can efficiently join two indices together and identify which component an index belongs to.

The solution approach is as follows:

  1. Initialize a union-find structure to keep track of the connected components. This structure will map an index to its root or representative index of its connected component.

  2. Iterate through the pairs and perform the union operation for each pair, effectively joining two indices into the same connected component.

  3. Organize the characters into groups by their root or representative index.

  4. Sort each group of characters in reverse lexicographical order. This makes it easier to pop the smallest character when rebuilding the string.

  5. Finally, build the result string by picking the smallest available character from each index's connected component. Since we sorted groups in reverse order, we pop characters from the end of each list, ensuring they are selected in increasing lexicographical order.

The provided function find is a helper function for the union-find structure that finds the root of an index, and during the process, applies path compression to keep the structure efficient by flattening the hierarchy (making each member of a component directly point to the root).

Learn more about Depth-First Search, Breadth-First Search, Union Find and Sorting patterns.

Solution Approach

The solution primarily utilizes the Union-Find algorithm and an efficient array-based approach to organize and sort the characters based on their connected components.

Here's the walkthrough of the solution approach:

  1. Initialization of Union-Find Structure: We begin by creating an array p which will act as the parent array for the Union-Find algorithm. Each element's initial value is its own index, implying that it is its own root.

    1p = list(range(n)) # n is the length of string s
  2. Union Operations: Iterate through the given pairs and perform the union operations. Instead of the traditional Union-Find with rank and path compression, the solution uses a simpler version that just assigns a new root to a component without considering the rank.

    1for a, b in pairs:
    2    p[find(a)] = find(b)

    The find function locates the root of an index and applies path compression by setting the p[x] entry directly to the root of p[x].

  3. Grouping Characters By Component: Once all pairs are processed, we need to group the characters according to their representative or root index. A dictionary d with default list values is used to append characters at the same group index.

    1d = defaultdict(list)
    2for i, c in enumerate(s):
    3    d[find(i)].append(c)
  4. Sorting Groups: Each list within dictionary d is sorted in reverse order. Sorting in reverse order enables us to pop elements from the end of the list later, which is faster than popping from the beginning.

    1for i in d.keys():
    2    d[i].sort(reverse=True)
  5. Rebuilding the String: The final string is formed by iterating over the original string's indices, finding the root of each index, and popping the smallest character from the corresponding group.

    1return "".join(d[find(i)].pop() for i in range(n))

The solution effectively groups indices of the string into connected components, sorts characters within each component, and then reconstructs the string by choosing the lexicographically smallest character available from each component for each position in the string. It's a smart application of the Union-Find algorithm and sorting to get the lexicographically smallest permutation satisfying the constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the solution approach with a string s = "dcab" and pairs pairs = [(0, 3), (1, 2)].

  1. Initialization of Union-Find Structure: We first initialize the parent array p for Union-Find. The string length n is 4, so p = [0, 1, 2, 3].

  2. Union Operations: Next, we perform union operations with the given pairs.

    • For pair (0, 3), we call find(0) and find(3) which return 0 and 3, and then we set p[0] to root of 3, which is 3. Now p = [3, 1, 2, 3].
    • For pair (1, 2), we call find(1) and find(2) which return 1 and 2, and then we set p[1] to root of 2, which is 2. Now p = [3, 2, 2, 3].
  3. Grouping Characters By Component: We group the characters by their roots. Resulting in d = {2: ['a', 'b'], 3: ['d', 'c']}.

  4. Sorting Groups: Sort each group in reverse order:

    • For group at root 2, sort ['a', 'b'] to get ['b', 'a'].
    • For group at root 3, sort ['d', 'c'] to get ['d', 'c']. Now we have d = {2: ['b', 'a'], 3: ['d', 'c']}.
  5. Rebuilding the String: We now rebuild the string by iterating over each index remembering to pop from the end of the list in order to maintain the lexicographical order.

    • For index 0, its root is 3, so we pop from d[3] to get 'c' (d[3] = ['d']).
    • For index 1, its root is 2, so we pop from d[2] to get 'a' (d[2] = ['b']).
    • For index 2, its root is also 2, so we pop again from d[2] to get 'b' (d[2] = []).
    • For index 3, its root is 3, so we pop from d[3] to get 'd' (d[3] = []).

Finally, the rebuilt string is "cabd", which is the lexicographically smallest string we can obtain through the allowed swaps.

The entire process utilizes the union-find algorithm to efficiently manage connected components and applies sorting to ensure the smallest characters are placed first. The resulting string is created by choosing the smallest character allowed by the swap operations at each index.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
5      
6        # Function to find the root of the set that element x belongs to
7        def find_root(x: int) -> int:
8            # Path compression: update parent to root for quicker access next time
9            if parent[x] != x:
10                parent[x] = find_root(parent[x])
11            return parent[x]
12
13        # Initialize the number of characters in the string
14        n = len(s)
15        # Initially, every character is in its own set
16        parent = list(range(n))
17
18        # Union operation: merge sets that are paired
19        for a, b in pairs:
20            # Set the parent of set a to be the root of set b, effectively merging the sets
21            parent[find_root(a)] = find_root(b)
22
23        # A dictionary to hold the characters by the root of the set they belong to
24        char_group = defaultdict(list)
25      
26        # Group all characters by their root
27        for i, c in enumerate(s):
28            char_group[find_root(i)].append(c)
29      
30        # Sort characters in each group in descending order to pop smallest char later
31        for chars in char_group.values():
32            chars.sort(reverse=True)
33      
34        # Build the smallest string by popping the smallest available character from the group
35        # the current position belongs to
36        output = "".join(char_group[find_root(i)].pop() for i in range(n))
37      
38        return output
39
1class Solution {
2    // The parent array for the disjoint set (Union-Find) data structure
3    private int[] parent;
4
5    /**
6     * Generates the smallest string resulting from swapping indices in pairs
7     *
8     * @param s The original string
9     * @param pairs A list of index pairs for swapping
10     * @return The lexicographically smallest string after swaps
11     */
12    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
13        int length = s.length();
14        parent = new int[length];
15        List<Character>[] disjointSets = new List[length];
16
17        // Initialize parent pointers to themselves and disjoint sets
18        for (int i = 0; i < length; ++i) {
19            parent[i] = i;
20            disjointSets[i] = new ArrayList<>();
21        }
22
23        // Join sets using union-find with the given pairs
24        for (var pair : pairs) {
25            int a = pair.get(0), b = pair.get(1);
26            parent[find(a)] = find(b);
27        }
28
29        // Distribute characters to corresponding sets
30        char[] chars = s.toCharArray();
31        for (int i = 0; i < length; ++i) {
32            disjointSets[find(i)].add(chars[i]);
33        }
34
35        // Sort each set in descending order (since we'll be removing from the end)
36        for (var set : disjointSets) {
37            set.sort((a, b) -> b - a);
38        }
39
40        // Build the result by choosing the last element in each set
41        for (int i = 0; i < length; ++i) {
42            var set = disjointSets[find(i)];
43            chars[i] = set.remove(set.size() - 1);
44        }
45
46        // Return the resultant string
47        return String.valueOf(chars);
48    }
49
50    /**
51     * Finds the root of the set x belongs to
52     *
53     * @param x The element to find the set of
54     * @return The root of the set containing x
55     */
56    private int find(int x) {
57        // Path compression for efficiency
58        if (parent[x] != x) {
59            parent[x] = find(parent[x]);
60        }
61        return parent[x];
62    }
63}
64
1class Solution {
2public:
3    // Function to generate the lexicographically smallest string possible by swapping indices given by pairs
4    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
5        int n = s.size();                // Length of the input string
6        vector<int> parent(n);           // Vector to keep track of the connected components
7        iota(parent.begin(), parent.end(), 0); // Initialize each node as its own parent to represent distinct sets
8        vector<vector<char>> charGroups(n); // Each index can store characters belonging to the same connected component
9        function<int(int)> find; // Declaration of the 'find' lambda function for finding the root of the set
10
11        // Lambda function that implements path compression for the disjoint set
12        find = [&](int x) -> int {
13            if (parent[x] != x) {
14                parent[x] = find(parent[x]);
15            }
16            return parent[x];
17        };
18
19        // Iterate over all pairs and perform the union operation to join the connected components
20        for (const auto& edge : pairs) {
21            int a = find(edge[0]), b = find(edge[1]);
22            parent[a] = b; // Merge the component of a with the component of b
23        }
24
25        // Group characters by the root of their connected component
26        for (int i = 0; i < n; ++i) {
27            charGroups[find(i)].push_back(s[i]); // Add character to its representative's group
28        }
29
30        // Sort the characters within each group in reverse order (since we will later pop elements from the end)
31        for (auto& group : charGroups) {
32            sort(group.rbegin(), group.rend());
33        }
34
35        // Construct the lexicographically smallest string by picking the smallest available character from each group
36        for (int i = 0; i < n; ++i) {
37            auto& group = charGroups[find(i)]; // Find the group of connected characters for the current index
38            s[i] = group.back(); // Assign the smallest character to the current index
39            group.pop_back(); // Remove the used character from the group
40        }
41
42        return s; // Return the lexicographically smallest string after swaps
43    }
44};
45
1// Function to find the smallest lexicographical string that can be obtained by swapping any pairs of indices.
2function smallestStringWithSwaps(s: string, pairs: number[][]): string {
3    const lengthOfString = s.length;
4    // Parent array for Union-Find to keep track of connected components
5    const parent = new Array(lengthOfString).fill(0).map((_, index) => index);
6
7    // Function to find the root parent of a component using path compression
8    const findRoot = (x: number): number => {
9        if (parent[x] !== x) {
10            parent[x] = findRoot(parent[x]);
11        }
12        return parent[x];
13    };
14
15    // Array of arrays to store characters belonging to the same connected component
16    const components: string[][] = new Array(lengthOfString).fill(0).map(() => []);
17
18    // Union-Find to connect components
19    for (const [a, b] of pairs) {
20        const rootA = findRoot(a);
21        const rootB = findRoot(b);
22        if (rootA !== rootB) {
23            parent[rootA] = rootB;
24        }
25    }
26
27    // Grouping the characters by their connected components
28    for (let i = 0; i < lengthOfString; ++i) {
29        components[findRoot(i)].push(s[i]);
30    }
31
32    // Sorting the characters in each component in descending order
33    // to access them in ascending order later using pop()
34    for (const component of components) {
35        component.sort((a, b) => b.charCodeAt(0) - a.charCodeAt(0));
36    }
37
38    // Array to build the final answer
39    const sortedString: string[] = [];
40    for (let i = 0; i < lengthOfString; ++i) {
41        // Retrieve and remove the last character from the sorted component
42        sortedString.push(components[findRoot(i)].pop()!);
43    }
44
45    // Join all characters to form the resulting string and return
46    return sortedString.join('');
47}
48

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into the following parts:

  1. Union-Find Initialization: Initializing the parent list p with n elements where n is the length of string s takes O(n) time.

  2. Union-Find Path Compression: For each pair in pairs, we potentially perform a union-by-rank and path compression. In the worst-case scenario, all elements can be connected, which ends up being nearly O(alpha(n)) per operation where alpha(n) is the Inverse Ackermann function. It is very slowly growing and is less than 5 for all practical values of n. Since there can be m pairs, this step takes at most O(m * alpha(n)) time.

  3. Grouping letters by connected components: Enumerating s and finding the root of each index takes O(n * alpha(n)) time. Appending characters to the corresponding lists in the dictionary d takes O(1) time per character, resulting in O(n) for this step.

  4. Sorting the letters: Each list in the dictionary d is sorted in reverse order. If k is the maximum size of the lists to be sorted, this step takes O(k * log(k)) time for each connected component. Since in the worst case there can be n/k such components, the overall sorting complexity can be O((n/k) * k * log(k)) = O(n * log(k)).

  5. Reconstructing the result string: Popping an element from each list in d and forming a new string takes O(n) time.

Summing these up, the worst-case time complexity of the algorithm is O(n + m * alpha(n) + n * alpha(n) + n * log(k) + n). Since alpha(n) is a very slow-growing function and can be considered constant for all practical purposes, and log(k) <= log(n), we can simplify this to O(n * log(n) + m).

Space Complexity

The space complexity can be broken down into the following:

  1. Parent array p: Uses O(n) space.

  2. Dictionary d: Contains at most n lists. In the worst case, each list has one character, so the total space taken by d is O(n).

  3. Auxiliary space for sorting: In the in-place sorting algorithm used by Python's .sort(), the space complexity is O(1). However, if we consider the space for the call stack due to recursive sorting algorithms in some implementations, this could give an additional space of O(log(k)) per connected component which sums up to O(n) in total.

Hence, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄