Smallest String With Swaps

Medium
675.

Smallest String With Swaps

Smallest String With Swaps is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google, Uber and PhonePe interviews.

You are given a string s and a list pairs of index pairs. You may swap the characters at any listed pair any number of times, in any order.

Return the lexicographically smallest string reachable this way.

Example 1

Input
s = "dcab", pairs = [[0,3],[1,2]]
Output
bacd
Explanation
Indices 0 and 3 can swap, as can 1 and 2, giving two independent pairs.

Example 2

Input
s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output
abcd
Explanation
The third pair links everything into one group, so all four characters can be sorted freely.

Example 3

Input
s = "cba", pairs = [[0,1],[1,2]]
Output
abc

Constraints

  • 1 <= s.length <= 100000
  • 0 <= pairs.length <= 100000
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
var smallestStringWithSwaps = function(s, pairs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest String With Swaps — Solution in Python, Java & C++

Smallest String With Swaps solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Smallest String With Swaps is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google, Uber and PhonePe interviews.

Problem statement

You are given a string s and a list pairs of index pairs. You may swap the characters at any listed pair any number of times, in any order.

Return the lexicographically smallest string reachable this way.

Example 1

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: bacd
Explanation: Indices 0 and 3 can swap, as can 1 and 2, giving two independent pairs.

Example 2

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: abcd
Explanation: The third pair links everything into one group, so all four characters can be sorted freely.

Example 3

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: abc

Constraints

  • 1 <= s.length <= 100000
  • 0 <= pairs.length <= 100000
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s consists of lowercase English letters.

Hints for Smallest String With Swaps

  1. Hint 1

    Repeated swaps mean the pairs define connected components of indices.

  2. Hint 2

    Within one component any permutation of its characters is reachable.

  3. Hint 3

    So sort each component's characters and write them back into that component's indices in sorted order.

How to solve Smallest String With Swaps

Swapping along edges any number of times generates every permutation within a connected component. So the smallest string sorts each component's multiset of characters into its component's sorted index list.

Approach

  1. Union the indices of every pair with a disjoint-set structure.
  2. Group the indices by their component root.
  3. For each group, collect its characters, sort them, and write them back into the group's indices in increasing index order.

Why it works

Transpositions along a connected graph generate the full symmetric group on its vertices, so any arrangement of a component's characters is reachable. Placing the smallest available character at the smallest index of the component is greedily optimal and cannot be beaten, because positions in different components are independent.

Complexity

  • Time — O(n log n + p α(n))
  • Space — O(n)

Pitfalls

  • Swapping only the listed pairs once misses arrangements that need a chain of swaps.
  • Sorting the whole string ignores the component boundaries and is wrong whenever the graph is disconnected.
  • Path compression matters: without it the union-find degrades badly at the stated limits.

Reference solution

Python

from typing import List

def smallestStringWithSwaps(s: str, pairs: List[List[int]]) -> str:
    n = len(s)
    parent = list(range(n))

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

    for a, b in pairs:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
    groups = {}
    for i in range(n):
        groups.setdefault(find(i), []).append(i)
    out = list(s)
    for idx in groups.values():
        chars = sorted(s[i] for i in idx)
        for t, i in enumerate(idx):
            out[i] = chars[t]
    return "".join(out)

Java

public static String smallestStringWithSwaps(String s, int[][] pairs) {
    int n = s.length();
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int[] p : pairs) {
        int a = findRoot(parent, p[0]);
        int b = findRoot(parent, p[1]);
        if (a != b) parent[a] = b;
    }
    Map<Integer, List<Integer>> groups = new HashMap<>();
    for (int i = 0; i < n; i++) groups.computeIfAbsent(findRoot(parent, i), z -> new ArrayList<>()).add(i);
    char[] out = s.toCharArray();
    for (List<Integer> idx : groups.values()) {
        char[] chars = new char[idx.size()];
        for (int t = 0; t < idx.size(); t++) chars[t] = s.charAt(idx.get(t));
        Arrays.sort(chars);
        for (int t = 0; t < idx.size(); t++) out[idx.get(t)] = chars[t];
    }
    return new String(out);
}

static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

C++

static int findRootSwap(vector<int>& parent, 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 = (int) s.size();
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (auto& p : pairs) {
        int a = findRootSwap(parent, p[0]);
        int b = findRootSwap(parent, p[1]);
        if (a != b) parent[a] = b;
    }
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) groups[findRootSwap(parent, i)].push_back(i);
    string out = s;
    for (auto& g : groups) {
        string chars;
        for (int i : g.second) chars += s[i];
        sort(chars.begin(), chars.end());
        for (size_t t = 0; t < g.second.size(); t++) out[g.second[t]] = chars[t];
    }
    return out;
}

JavaScript

var smallestStringWithSwaps = function(s, pairs) {
    var n = s.length;
    var parent = [];
    for (var t = 0; t < n; t++) parent.push(t);
    var find = function(x) {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    for (var p = 0; p < pairs.length; p++) {
        var a = find(pairs[p][0]), b = find(pairs[p][1]);
        if (a !== b) parent[a] = b;
    }
    var groups = {};
    for (var i = 0; i < n; i++) {
        var r = String(find(i));
        if (groups[r] === undefined) groups[r] = [];
        groups[r].push(i);
    }
    var out = s.split("");
    var keys = Object.keys(groups);
    for (var k = 0; k < keys.length; k++) {
        var idx = groups[keys[k]];
        var chars = [];
        for (var m = 0; m < idx.length; m++) chars.push(s.charAt(idx[m]));
        chars.sort();
        for (var q = 0; q < idx.length; q++) out[idx[q]] = chars[q];
    }
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets