Smallest String With Swaps - Leetcode Solution

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"

Solution:

The problem states that we can swap characters at any pair of indices in the given pairs any number of times.

The brute force solution is to create all possible combinations of swaps and check which yields the lexicographically smallest string. But this solution has exponential time complexity and is not feasible, especially for large input size.

We can represent the given pairs of indices as a graph where each index is a node and each pair specifies an edge between the nodes. All nodes that are connected form a connected component.

We can then group the characters in s based on their connected component and sort each group in ascending order.

Using a union-find algorithm, we can find all connected components and their corresponding indices. We can then sort the characters within each component and rebuild the string based on the sorted order.

Algorithm:

1. Create an empty hashmap "component".

2. Traverse pairs, and for each pair(p), do the following a. Add p[0] and p[1] as keys to the hashmap if they do not exist already, and assign the other as their values. b. If p[0] or p[1] exists in the hashmap and has a value, update all the keys that point to the value to point to the key of this pair.

3. Create an empty hashmap "group".

4. Traverse s. For each s[i], do the following a. Get a reference to the values of the component hashmap for the node i. b. If there is no reference, decrement index counter for group. c. If there is reference, get(or create and get) an array list from the group hashmap with index as reference. d. Add the character s[i] to the array list.

5. Traverse the group hashmap. For each array list, do the following a. Sort the array list in ascending order. b. Traverse the array list, and for each element, set c to the character at the index i from the group hashmap, and increment i. c. Build the lexicographically smallest string.

Time Complexity:

The time complexity of building the graph is O(nlogn) + O(mlogm), where n is the length of s and m is the length of pairs.

The time complexity of creating groups is O(nlogn).

The time complexity of sorting each character group is O(nlogn).

The time complexity of rebuilding the string is O(n).

Hence, the total time complexity of the solution is O(nlogn) + O(mlogm).

1