Smallest String With Swaps

medium union find graph sorting

Problem

You are given a string s and an array of pairs of indices pairs where pairs[i] = [a, b] indicates that you may swap the characters at index a and index b any number of times. Return the lexicographically smallest string that s can be transformed into.

Inputs = "dcab", pairs = [[0,3],[1,2]]

Output"bacd"

Swap s[0] and s[3] → "bcad", then s[1] and s[2] → "bacd". Indices {0,3} form one group and {1,2} another; within each group characters can be reordered freely.

pairs (e.g. 0-3, 1-2)

def smallest_string_with_swaps(s, pairs):
    n = len(s)
    parent = list(range(n))

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

    for a, b in pairs:
        parent[find(a)] = find(b)

    groups = {}
    for i in range(n):
        groups.setdefault(find(i), []).append(i)

    res = list(s)
    for idxs in groups.values():
        chars = sorted(res[i] for i in idxs)
        for i, c in zip(sorted(idxs), chars):
            res[i] = c
    return "".join(res)

function smallestStringWithSwaps(s, pairs) {
  const n = s.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  for (const [a, b] of pairs) parent[find(a)] = find(b);

  const groups = new Map();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (!groups.has(r)) groups.set(r, []);
    groups.get(r).push(i);
  }

  const res = s.split("");
  for (const idxs of groups.values()) {
    const chars = idxs.map(i => res[i]).sort();
    const sorted = idxs.slice().sort((a, b) => a - b);
    sorted.forEach((i, k) => { res[i] = chars[k]; });
  }
  return res.join("");
}

class Solution {
    int[] parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (List<Integer> p : pairs) parent[find(p.get(0))] = find(p.get(1));

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

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

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
        for (auto& p : pairs) parent[find(p[0])] = find(p[1]);

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

        for (auto& kv : groups) {
            auto& idxs = kv.second;
            string chars;
            for (int i : idxs) chars += s[i];
            sort(chars.begin(), chars.end());
            for (int k = 0; k < (int)idxs.size(); k++) s[idxs[k]] = chars[k];
        }
        return s;
    }
};

Explanation

The key insight is that if you can swap index a with b, and b with c, then by chaining swaps you can rearrange the characters at a, b, and c into any order you like. So each connected group of swappable indices can be reordered freely.

That makes this a connected components problem. We treat each pair as an edge and use union-find to merge indices that are linked, directly or through a chain.

Once the groups are known, the smallest string is easy: inside each group, take the characters there, sort them, and place the smallest letters at the smallest indices. Doing this for every group gives the lexicographically smallest overall result.

find(x) walks up to a group's root, and parent[find(a)] = find(b) merges two groups. Then groups collects all indices sharing a root.

Example: s = "dcab", pairs [[0,3],[1,2]]. Indices {0,3} hold d,b which sort to b,d; indices {1,2} hold c,a which sort to a,c. The result is "bacd".

Time: O(n log n + p) Space: O(n)