Vultr DocsLatest Content

Smallest String With Swaps

Updated on 24 June, 2025
Smallest String With Swaps header image

Problem Statement

In this challenge, you are provided with a string s and a collection of index pairs pairs. Each pair within pairs consists of two indices that represent positions within the string s. You are allowed to swap characters at these paired indices multiple times. The core task is to determine the lexicographically smallest string that can be obtained from s by making these swaps. This means sorting the string in such a way that it appears before others in a dictionary.

Examples

Example 1

Input:

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

Output:

"bacd"

Explanation:

Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2

Input:

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

Output:

"abcd"

Explanation:

Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3

Input:

s = "cba", pairs = [[0,1],[1,2]]

Output:

"abc"

Explanation:

Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s only contains lowercase English letters.

Approach and Intuition

Understanding how to convert the problem of forming the lexicographically smallest string via index swapping can be complex, but can be tackled effectively with graph theory and connected components.

Basic Idea

  1. Construct a Graph:

    • Treat each character position in the s as a node.
    • A pair [a, b] in pairs represents an undirected edge in the graph between node a and node b.
    • Therefore, if you can travel from node a to node b through a series of swaps (edges), they belong to the same connected component.

  2. Identify Connected Components:

    • Use a Union-Find data structure (Disjoint Set Union) or Depth-First Search (DFS) to find and group all indices that are connected directly or indirectly via pairs.
    • Nodes in the same connected component can have their characters swapped amongst themselves in any order.

  3. Reconstruct the String:

    • For each connected component:

      • Extract the characters from s at the indices in the component.
      • Sort the characters.
      • Reassign them back to the corresponding indices in sorted order.

  4. Construct Final String:

    • After processing all connected components, join the characters to return the final string.

Considerations

  • Complexity:

    • Union-Find operations are nearly linear with path compression.
    • Sorting characters in each component is efficient since total characters = length of s.
    • Overall complexity is approximately O(N log N) which is acceptable for N up to $10^5$.

  • Edge Cases:

    • No swaps allowed → return s directly.
    • All characters identical → swapping won’t change output.
    • Redundant or overlapping pairs → form a larger component, handled naturally by Union-Find or DFS.

This graph-based approach ensures correctness and efficiency under all constraints.

Solutions

  • C++
  • Java
cpp 
class DisjointSet {
private:
    vector<int> parent;
    vector<int> size;
public:
    DisjointSet(int count) : parent(count), size(count) {
        for (int i = 0; i < count; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    int findRoot(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = findRoot(parent[x]);
    }

    void unionGroups(int x, int y) {
        int root1 = findRoot(x);
        int root2 = findRoot(y);
        if (root1 != root2) {
            if (size[root1] >= size[root2]) {
                parent[root2] = root1;
                size[root1] += size[root2];
            } else {
                parent[root1] = root2;
                size[root2] += size[root1];
            }
        }
    }
};

class Solver {
public:
    string optimizeString(string inputString, vector<vector<int>>& edges) {
        DisjointSet ds(inputString.size());
        
        for (vector<int> edge : edges) {
            int start = edge[0];
            int end = edge[1];
            ds.unionGroups(start, end);
        }
        
        unordered_map<int, vector<int>> clusterRef;
        for (int node = 0; node < inputString.size(); node++) {
            int root = ds.findRoot(node);
            clusterRef[root].push_back(node);
        }
        
        string result(inputString.size(), ' ');
        for (auto &cluster : clusterRef) {
            vector<int> nodeIdx = cluster.second;
            vector<char> chars;
            for (int idx : nodeIdx) {
                chars.push_back(inputString[idx]);
            }
            sort(chars.begin(), chars.end());
            
            for (int idx = 0; idx < nodeIdx.size(); idx++) {
                result[nodeIdx[idx]] = chars[idx];
            }
        }
        
        return result;
    }
};

The Smallest String with Swaps problem involves restructuring a string through specific allowed swaps represented as edges between indices. The solution uses a combination of a disjoint set (DSU) to manage connected components (groups of characters that can be swapped) and sorting mechanisms to rearrange the characters into the lexographically smallest order possible within the constraints.

The provided C++ solution encapsulates the functionality within two main classes:

  • DisjointSet: Manages groups of indices where each group can have characters swapped amongst themselves.

    • Initializes each index as its own parent and establishes size metrics for optimization.
    • Implements findRoot to find the ultimate parent (representative member) of a component. This method employs path compression to flatten the structure, enhancing efficiency.
    • Implements unionGroups to merge two components, ensuring that smaller components get merged under larger ones to maintain minimal height for efficient traversal.

  • Solver:

    • Utilizes the DisjointSet in the optimizeString method by first connecting indices as dictated by the list of edges.
    • Maps all indices in the string to their root parent, using this to group indices into components.
    • For each component, retrieves the characters, sorts them, and places them back into the string in their original positions but in sorted order to achieve the smallest lexicographical sequence.

The approach offers an efficient mechanism to optimize the string as:

  1. The disjoint set abstracts component management, highly optimizing group formations with quasi-linear complexity.
  2. Sorting individual groups and placing them back maintains the smallest order effectively.

This design leverages data structures and algorithms efficiently to address the challenge of forming the lexicographically smallest string under swap constraints, ensuring both high performance and correctness in rebuilding the string.

java 
class Solution {
    public String reorderSmallestString(String str, List<List<Integer>> swapPairs) {
        DisjointSet ds = new DisjointSet(str.length());

        // Process each swap pair
        for (List<Integer> pair : swapPairs) {
            int first = pair.get(0);
            int second = pair.get(1);
            
            // Connect the two indices in set
            ds.connect(first, second);
        }
        
        Map<Integer, List<Integer>> componentMap = new HashMap<>();
        // Group indices by component root
        for (int i = 0; i < str.length(); i++) {
            int root = ds.find(i);
            // Create list for the component if it doesn't exist
            componentMap.putIfAbsent(root, new ArrayList<>());
            componentMap.get(root).add(i);
        }
        
        // Result string as character array
        char[] result = new char[str.length()];
        // Process each component
        for (List<Integer> component : componentMap.values()) {
            // List to store characters by index
            List<Character> chars = new ArrayList<>();
            for (int idx : component) {
                chars.add(str.charAt(idx));
            }
            Collections.sort(chars); // Sort characters to form smallest string
            
            // Place sorted characters back to result
            for (int j = 0; j < component.size(); j++) {
                result[component.get(j)] = chars.get(j);
            }
        }
        
        return new String(result);
    }
}

class DisjointSet {
    private int[] parent;
    private int[] size;

    // Constructor to initialize the disjoint set
    public DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // Find the root of the set containing x
    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]); // Path compression
    }

    // Union by size: attach smaller tree under larger tree
    public void connect(int x, int y) {
        int root1 = find(x);
        int root2 = find(y);
        if (root1 != root2) {
            if (size[root1] >= size[root2]) {
                parent[root2] = root1;
                size[root1] += size[root2];
            } else {
                parent[root1] = root2;
                size[root2] += size[root1];
            }
        }
    }
}

This Java solution tackles the problem of finding the smallest lexicographical string achievable through specific swaps. The primary approach leverages the concept of a Disjoint Set (Union-Find) to efficiently track and manage the connectivity between elements as defined by the swap pairs.

  • Initialize a DisjointSet class to manage connectivity between indices of the string.
  • For each pair in the swap list, utilize the connect method to establish a link between the two indices.
  • Use a HashMap to group the index components, associating each index with their respective root in the disjoint set.
  • For each uniquely identified component, extract the corresponding characters from the string, sort them, and reassign them back to their positions to ensure the lexicographically smallest order.
  • Finally, combine the sorted characters to form the result string.

This approach ensures that the functionality of the reorderSmallestString method effectively rearranges characters in such a way that, leveraging the swap operations defined, the smallest possible string is returned. This method handles the core string manipulation and sorting logic while the disjoint set operations craft an efficient way to manage and understand component relationships.

Comments

No comments yet.