🌱 Keegan's Digital Garden

1202. Smallest String With Swaps

3 min read

πŸ“ Problem Details

πŸ€”What Did I Struggle With?

- graph representation of the problem 
- understanding the disjoint sets approach to the problem

πŸ’‘ Explanation of Solution

Visualizing the Problem as a Graph Problem

  • Nodes: each index of string s is representing as a node
  • Edges: each pair [i,j] is an edge between nodes i and j, indicating that characters at these indices can be swapped
  • Connected Components: All indices that are connected directly or indirectly through edges form a connected component
    • Within each connected component, you can freely rearrange the characters

Identifying Disjoint Sets in the Graph

  • a Disjoint Set (Union-Find (Disjoint Set)) is a collection of indices that belong to the same connected component in the graph
    • these sets represent groups of indices where swaps can occur

Algorithm Design

- graph representation
	- treat indices of the string as nodes and pairs as edges to form an undirected graph

- find connected components
	- ue union-find to efficiently group indicies into connected components

- collect and sort characters
	- for each connected component, collect the characters from the string corresponding to the indices
	- sort the characters lexicographically

- reassign sorted characters
	- map the sorted characters back to the corresponding indices in the string

βŒ› Complexity Analysis

Time Complexity: O(n log n)
- sorting characters within components takes O(n log n)
- disjoint set operations 
	- initialising parent and rank structures takes O(n)
	- union operation is O(Ξ±(n)) where Ξ± is the inverse ackermann function (almost constant)

Space Complexity: O(n)
- storage of indices in the disjoint set --> O(n)
- storage of connected components in a hashmap --> O(n)

πŸ’» Implementation of Solution

```cpp
class UnionFind {
private:
    vector<int> parent; // stores the parent of each element
    vector<int> rank;   // stores the rank(depth) of each set
 
public:
    // constructor initializes n elements with each element being its own parent
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // Initially, each element is its own root
        }
    }
 
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }
 
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
 
        if (rootX != rootY) {
            // Union by Rank
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }
};
 
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        UnionFind uf(n);
 
        // step 1: union nodes based on pairs
        for(const auto& pair : pairs) {
            uf.unionSets(pair[0], pair[1]);
        }
 
        // step 2: group indices by their connected component
        unordered_map<int, vector<int>> components;
        for(int i=0; i < n; i++) {
            components[uf.find(i)].push_back(i);
        }
 
        // step 3: sort characters within each connected component
        for(auto& [root, indices] : components) {
            // collect characters
            string chars;
            for(int index : indices) {
                chars += s[index];
            }
 
            // sort characters
            sort(chars.begin(), chars.end());
 
            // reassign sorted characters back to their positions
            sort(indices.begin(), indices.end());
 
            for(int i=0; i < indices.size(); i++) {
                s[indices[i]] = chars[i];
            }
        }
        return s;
    }
};

Graph View