algoadvance

Leetcode 3216. Lexicographically Smallest String After a Swap

Problem Statement

Given a string s and a list of pairs of indices in the string pairs where pairs[i] = [a, b] indicates you can swap the characters at index a and index b of the string s. You can swap the characters at any given index pair any number of times. Return the lexicographically smallest string that s can be after using the swaps.

Clarifying Questions

  1. What are the constraints on the length of the string s and the number of pairs pairs?
    • Let’s assume s can have a length up to 100000 and pairs can have up to 100000 pairs.
  2. Can we have duplicate pairs in pairs?
    • Yes, duplicates can exist but they don’t affect the result since swapping the same pair multiple times doesn’t change its impact.
  3. What characters can be in the string s?
    • The string s contains only lowercase English letters.

Strategy

  1. Union-Find Approach:
    • The idea is to treat the swapping pairs as edges in a graph where each node represents an index in the string. The connected components in this graph represent indices that can be freely swapped among each other.
  2. Find Components:
    • Use the Union-Find algorithm to group indices that can be reached from one another through a series of swaps.
  3. Sort Each Component:
    • For each connected component, extract the characters, sort them, and place them back in the original string in the lexicographically smallest order.

Code

#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;

class UnionFind {
public:
    UnionFind(int n): parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // path compression
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};

string smallestStringWithSwaps(string s, vector<pair<int, int>>& pairs) {
    int n = s.size();
    UnionFind uf(n);

    // Union step
    for (const auto& p : pairs) {
        uf.unite(p.first, p.second);
    }

    // Group all characters by their root index
    unordered_map<int, vector<int>> rootToNodes;
    for (int i = 0; i < n; ++i) {
        int root = uf.find(i);
        rootToNodes[root].push_back(i);
    }

    // Sort each group and place back their characters to the original string
    for (auto& entry : rootToNodes) {
        vector<int>& indices = entry.second;
        string temp;
        for (int index : indices) {
            temp += s[index];
        }
        sort(temp.begin(), temp.end());
        sort(indices.begin(), indices.end());

        for (int i = 0; i < indices.size(); ++i) {
            s[indices[i]] = temp[i];
        }
    }

    return s;
}

Time Complexity

Thus, the overall time complexity of the solution is O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI