# Smallest String With Swaps
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-string-with-swaps)
Canonical: https://scaleengineer.com/dsa/problems/smallest-string-with-swaps
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, String
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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.

# Approaches
## Graph Traversal using DFS
This approach treats the problem as finding connected components in a graph. Indices are vertices, and swappable pairs are edges. For each component, we sort the characters and place them in the sorted index positions to get the lexicographically smallest result.
**Time:** O(P + N log N), where N is the length of the string and P is the number of pairs. Building the graph takes O(N + P). The DFS traversal over all nodes and edges takes O(N + P). Sorting the elements within each component takes Σ(k_i * log(k_i)) where k_i is the size of component i. In the worst case, this is O(N log N). The total complexity is dominated by the traversal and sorting, resulting in O(P + N log N). · **Space:** O(N + P). The adjacency list requires O(N + P) space. The `visited` array and recursion stack for DFS require O(N) space. The lists for storing component data also require O(N) space in the worst case.
**Pros:** Conceptually straightforward, directly modeling the problem.; Works for all cases and is a standard graph algorithm application.
**Cons:** Requires building an explicit graph structure, which can use more memory.; Slightly less efficient than the Union-Find approach due to higher space complexity and potentially higher constant factors in time.
### Explanation
We can model the swappable indices as a graph. The indices of the string `s` are the vertices, and each pair `[u, v]` in `pairs` represents an undirected edge between vertex `u` and `v`. The problem states we can swap characters any number of times. This implies that within any connected component of this graph, we can arrange the characters in any order. To get the lexicographically smallest string, for each connected component, we should arrange its characters in ascending order and place them at the indices of that component, also in ascending order.

We can find these components using a graph traversal algorithm like Depth-First Search (DFS). We iterate through each index from `0` to `n-1`. If we find an index that we haven't visited yet, we start a DFS from it. The DFS explores the entire component, collecting all its indices and the corresponding characters. After the traversal for one component is complete, we sort the collected indices and characters. Then, we map the i-th smallest character to the i-th smallest index position in our result. We repeat this until all indices have been visited.

```java
import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> pair : pairs) {
            int u = pair.get(0);
            int v = pair.get(1);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        char[] result = new char[n];
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> componentIndices = new ArrayList<>();
                List<Character> componentChars = new ArrayList<>();
                
                dfs(i, s, adj, visited, componentIndices, componentChars);
                
                Collections.sort(componentIndices);
                Collections.sort(componentChars);
                
                for (int j = 0; j < componentIndices.size(); j++) {
                    result[componentIndices.get(j)] = componentChars.get(j);
                }
            }
        }
        return new String(result);
    }

    private void dfs(int u, String s, List<List<Integer>> adj, boolean[] visited, List<Integer> indices, List<Character> chars) {
        visited[u] = true;
        indices.add(u);
        chars.add(s.charAt(u));
        
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfs(v, s, adj, visited, indices, chars);
            }
        }
    }
}
```
### Algorithm
- Build an adjacency list for the graph from the `pairs`.
- Create a `visited` array to track processed indices.
- Iterate from index `0` to `n-1`. If an index `i` is unvisited, start a DFS.
- The DFS will find all indices and characters in the current connected component.
- Sort the collected indices and characters for the component.
- Place the sorted characters at the sorted index positions in a result array.
- Convert the result array to the final string.

## Disjoint Set Union (DSU) / Union-Find
A more efficient approach using the Union-Find data structure to find the connected components. This avoids building an explicit graph. After grouping indices into sets using Union-Find, we process each set (component) by sorting its characters and placing them into the corresponding sorted indices.
**Time:** O(P * α(N) + N log N), where N is the string length, P is the number of pairs, and α is the Inverse Ackermann function. The Union-Find operations take O(P * α(N)). Grouping indices takes O(N * α(N)). The dominant step is sorting characters for each component, which has a total complexity of O(N log N) in the worst case. · **Space:** O(N). The DSU data structure (`parent` and `rank` arrays) requires O(N) space. The map used for grouping indices and characters also requires O(N) total space, as each index and character is stored once across all map values.
**Pros:** Highly efficient for finding connected components.; Better space complexity (O(N)) compared to the explicit graph approach.; Implementation is often cleaner and faster in practice.
**Cons:** Requires familiarity with the Union-Find data structure and its implementation.
### Explanation
The Union-Find (or Disjoint Set Union) data structure is highly optimized for problems that involve partitioning elements into disjoint sets, which is exactly what we need to do with the string indices. Each swappable pair `[u, v]` indicates that indices `u` and `v` belong to the same set (or connected component).

We start by initializing a DSU structure where each index `0` to `n-1` is in its own set. Then, we iterate through all the `pairs` and call `union(u, v)` for each pair. This efficiently merges the sets. We use optimizations like path compression and union by rank/size to make these operations nearly constant time on average.

After processing all pairs, the DSU structure contains the component information. We can then iterate through all indices `i` from `0` to `n-1`, use `find(i)` to get the representative (root) of its component, and group all indices with the same root. A `HashMap` is ideal for this, mapping each root to a list of its member indices.

Finally, for each component (each list of indices in our map), we gather the corresponding characters from the original string `s`, sort both the indices and the characters, and then place the sorted characters into the correct positions in a result array. This ensures the lexicographically smallest arrangement for each component.

```java
import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);

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

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

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

        return new String(result);
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
        }
    }
}
```
### Algorithm
- Initialize a Union-Find data structure for `n` indices.
- Iterate through `pairs`, performing a `union` operation for each pair to merge their sets.
- Create a map to group indices by their component's root.
- Iterate from index `0` to `n-1`, find the root for each index `i`, and add `i` to the list associated with its root in the map.
- For each component in the map:
  - a. Collect the characters corresponding to the indices in the component.
  - b. Sort the list of indices and the list of characters.
  - c. Place the sorted characters into a result array at the sorted index positions.
- Convert the result array to the final string.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    int n = s.length();
    p = new int[n];
    List<Character>[] d = new List[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      d[i] = new ArrayList<>();
    }
    for (var pair : pairs) {
      int a = pair.get(0), b = pair.get(1);
      p[find(a)] = find(b);
    }
    char[] cs = s.toCharArray();
    for (int i = 0; i < n; ++i) {
      d[find(i)].add(cs[i]);
    }
    for (var e : d) {
      e.sort((a, b)->b - a);
    }
    for (int i = 0; i < n; ++i) {
      var e = d[find(i)];
      cs[i] = e.remove(e.size() - 1);
    }
    return String.valueOf(cs);
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### Python

```python
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(s) p = list(range(n)) for a, b in pairs: p[find(a)] = find(b) d = defaultdict(list) for i, c in enumerate(s): d[find(i)]. append(c) for i in d . keys(): d[i]. sort(reverse=True) return "" . join(d[find(i)]. pop() for i in range(n))

```

### CPP

```cpp
class Solution {
public:
  string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {
    int n = s.size();
    int p[n];
    iota(p, p + n, 0);
    vector<char> d[n];
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    for (auto e : pairs) {
      int a = e[0], b = e[1];
      p[find(a)] = find(b);
    }
    for (int i = 0; i < n; ++i) {
      d[find(i)].push_back(s[i]);
    }
    for (auto &e : d) {
      sort(e.rbegin(), e.rend());
    }
    for (int i = 0; i < n; ++i) {
      auto &e = d[find(i)];
      s[i] = e.back();
      e.pop_back();
    }
    return s;
  }
};

```