Crack the Backend

Problem Statement

You are given a string s and a list of index pairs pairs[i] = [a, b]. You may swap characters at s[a] and s[b] any number of times (and use other pairs as well). Return the lexicographically smallest string you can obtain.

Key Observations

Union Find on indices: Union every pair (i, j) — indices in the same connected component can be reordered arbitrarily (any permutation via swaps). So for each component, we have a set of indices and a set of characters; the smallest string assigns the smallest character to the smallest index in that component. So: group indices by root; for each group collect the characters at those indices, sort the characters and sort the indices; assign the i-th smallest char to the i-th smallest index.

Approach

High-level: UF on 0..n-1. For each (i,j) union(i,j). Group indices by find(i); for each group: indices list and chars list, sort both, assign sorted chars to sorted indices. Build result string.

Steps: UF parent = new int[n]; for (List<Integer> p : pairs) union(p.get(0), p.get(1)); Map<Integer, List<Integer>> rootToIndices; for (i=0;i<n;i++) rootToIndices.computeIfAbsent(find(i), k->new ArrayList<>()).add(i); For each group: sort indices, collect chars and sort, fill result[indices.get(i)] = sortedChars.get(i). return new String(result);

Implementation

Java

public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    int n = s.length();
    int[] parent = new int[n];

    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

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

    Map<Integer, List<Integer>> groups = new HashMap<>();

    for (int i = 0; i < n; i++)
    groups.computeIfAbsent(find(parent, i), k -> new ArrayList<>()).add(i);
    char[] arr = s.toCharArray();

    for (List<Integer> idx : groups.values()) {
        List<Character> chars = new ArrayList<>();

        for (int i : idx) {
            chars.add(arr[i]);
        }

        Collections.sort(chars);
        Collections.sort(idx);

        for (int k = 0; k < idx.size(); k++) {
            arr[idx.get(k)] = chars.get(k);
        }
    }

    return new String(arr);
}

Test Cases

Example 1

Input

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

Expected

"bacd"

Explanation

Swap to get smallest.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.