D
DevExCode

LeetCode 1202: Smallest String With Swaps Solution

Master LeetCode problem 1202 (Smallest String With Swaps), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a disjoint set union (DSU) data structure. We first build connected components based on the pairs of indices provided. Then, for each connected component, we sort the characters within that component. Finally, we map the sorted characters back to their original indices to form the lexicographically smallest string.

Algorithm:

  1. Create a DSU data structure with operations: find(x) and union(x, y).
  2. Iterate over the pairs array and union the indices in each pair.
  3. Create a map to group together characters that belong to the same connected component.
  4. Sort the characters within each connected component.
  5. Create the final result string by mapping the sorted characters back to their original indices.

Time Complexity:

The time complexity of this approach is O(n log n), where n is the length of the input string s.

Space Complexity:

The space complexity is O(n) for the DSU data structure and the map used to group characters.

Solution Code

class Solution {
    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> pair : pairs) {
            int x = find(parent, pair.get(0));
            int y = find(parent, pair.get(1));
            if (x != y) {
                parent[x] = y;
            }
        }
        
        Map<Integer, List<Character>> components = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = find(parent, i);
            components.computeIfAbsent(root, k -> new ArrayList<>()).add(s.charAt(i));
        }
        
        for (List<Character> chars : components.values()) {
            Collections.sort(chars);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int root = find(parent, i);
            List<Character> chars = components.get(root);
            sb.append(chars.remove(0));
        }
        
        return sb.toString();
    }
    
    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1202 (Smallest String With Swaps)?

This page provides optimized solutions for LeetCode problem 1202 (Smallest String With Swaps) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1202 (Smallest String With Swaps)?

The time complexity for LeetCode 1202 (Smallest String With Swaps) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1202 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1202 in Java, C++, or Python.

Back to LeetCode Solutions