What is the time complexity of Smallest String With Swaps?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Smallest String With Swaps?

This problem uses Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Smallest String With Swaps?

Insight 1: The 'pairs' array defines connected components in the string. Indices within a component can be freely swapped. Insight 2: Union-Find (Disjoint Set) data structure is effective for identifying connected components.

Which companies ask LeetCode 1202. Smallest String With Swaps in interviews?

This problem is frequently asked at PhonePe.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Smallest String With Swaps - LeetCode 1202 Solution

Smallest String With Swaps - Complete Solution Guide

Smallest String With Swaps is LeetCode problem 1202, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a string s , and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times . Return the lexicographically smallest string that s can be changed to after using the swaps. Example 1: Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2: Input: s =

Detailed Explanation

The problem asks us to find the lexicographically smallest string that can be formed from a given string `s` by swapping characters at indices specified in the `pairs` array. We can swap characters at any pair of indices in `pairs` any number of times. The pairs represent connected components within the string. The goal is to rearrange characters within each connected component to produce the smallest possible string. For example, if we have 'dcab' and pairs [[0,3],[1,2]], then index 0 and 3 can swap, as well as 1 and 2. We can swap 'd' with 'b' to get 'bcad', and then 'c' with 'a' to get 'bacd'.

Solution Approach

The solution uses the Union-Find data structure to identify connected components within the string based on the given pairs of indices. For each connected component, it gathers the characters and their original indices. Then, it sorts both the characters and the indices. Finally, it reconstructs the string by placing the sorted characters at their corresponding sorted indices within the result string. This ensures that the smallest characters are placed at the smallest indices within each connected component.

Step-by-Step Algorithm

Step 1: Initialize a Union-Find data structure (parent array and size array) to track connected components. Initially, each index is its own parent, representing separate components.
Step 2: Iterate through the `pairs` array and perform the `union` operation on each pair of indices. The `union` operation merges the connected components of the two indices.
Step 3: Create a dictionary (or HashMap in Java/C++) to store connected components. The key is the root (parent) of the component, and the value is a tuple (or pair) of two lists: a list of indices and a list of characters belonging to that component.
Step 4: Iterate through the string `s` and, for each index, find the root of its connected component. Add the index and the corresponding character to the appropriate lists in the dictionary.
Step 5: Iterate through the dictionary of connected components. For each component, sort the list of indices and the list of characters in ascending order.
Step 6: Create a new string (or character array) to store the result. Iterate through the sorted lists of indices and characters for each component, and place each character at its corresponding index in the result string.
Step 7: Convert the resulting character array (or string) and return it.

Key Insights

Insight 1: The 'pairs' array defines connected components in the string. Indices within a component can be freely swapped.
Insight 2: Union-Find (Disjoint Set) data structure is effective for identifying connected components.
Insight 3: Sorting the indices and characters within each component allows creating the lexicographically smallest string.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find, Sorting.

Companies

Asked at: PhonePe.

Smallest String With Swaps | LeetCode 1202

Medium

Array Hash Table String Depth-First Search Breadth-First Search Union Find Sorting

Time: O(n log n)Space: O(n)

Solution Code

Available in:

import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        function find(i) {
            if (parent[i] == i) {
                return i;
            }
            parent[i] = find(parent[i]);
            return parent[i];
        }

        function union(i, j) {
            int root_i = find(i);
            int root_j = find(j);
            if (root_i != root_j) {
                if (size[root_i] < size[root_j]) {
                    int temp = root_i;
                    root_i = root_j;
                    root_j = temp;
                }
                parent[root_j] = root_i;
                size[root_i] += size[root_j];
            }
        }

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

        Map<Integer, List<Integer>> componentIndices = new HashMap<>();
        Map<Integer, List<Character>> componentChars = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int root = find(i);
            if (!componentIndices.containsKey(root)) {
                componentIndices.put(root, new ArrayList<>());
                componentChars.put(root, new ArrayList<>());
            }
            componentIndices.get(root).add(i);
            componentChars.get(root).add(s.charAt(i));
        }

        char[] res = s.toCharArray();
        for (int root : componentIndices.keySet()) {
            List<Integer> indices = componentIndices.get(root);
            List<Character> chars = componentChars.get(root);

            Collections.sort(indices);
            Collections.sort(chars);

            for (int i = 0; i < indices.size(); i++) {
                res[indices.get(i)] = chars.get(i);
            }
        }

        return new String(res);
    }

    private int find(int i, int[] parent) {
        if (parent[i] == i) {
            return i;
        }
        parent[i] = find(parent[i], parent);
        return parent[i];
    }

    private void union(int i, int j, int[] parent, int[] size) {
        int root_i = find(i, parent);
        int root_j = find(j, parent);
        if (root_i != root_j) {
            if (size[root_i] < size[root_j]) {
                int temp = root_i;
                root_i = root_j;
                root_j = temp;
            }
            parent[root_j] = root_i;
            size[root_i] += size[root_j];
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1202: Smallest String With Swaps - Detailed explanation and solution approaches.

Topics

Array Hash Table String Depth-First Search Breadth-First Search Union Find Sorting

Companies

PhonePe

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1202

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a Union-Find data structure (parent array and size array) to track connected components. Initially, each index is its own parent, representing separate components.
2
Step 2: Iterate through the `pairs` array and perform the `union` operation on each pair of indices. The `union` operation merges the connected components of the two indices.
3
Step 3: Create a dictionary (or HashMap in Java/C++) to store connected components. The key is the root (parent) of the component, and the value is a tuple (or pair) of two lists: a list of indices and a list of characters belonging to that component.
4
Step 4: Iterate through the string `s` and, for each index, find the root of its connected component. Add the index and the corresponding character to the appropriate lists in the dictionary.
5
Step 5: Iterate through the dictionary of connected components. For each component, sort the list of indices and the list of characters in ascending order.
6
Step 6: Create a new string (or character array) to store the result. Iterate through the sorted lists of indices and characters for each component, and place each character at its corresponding index in the result string.
7
Step 7: Convert the resulting character array (or string) and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the sorting step. The Union-Find operations contribute a close to constant factor due to path compression. The space complexity is determined by the parent array, size array, component dictionary and the result string.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

Use DFS to find connected components. For each unvisited index, perform a DFS to find all indices in its connected component. Collect the characters and indices, sort them, and update the result string.

Time: O(n log n)Space: O(n)

Trade-offs: DFS might be more intuitive for some, but Union-Find is often considered slightly more efficient in practice due to its amortized constant time complexity for union and find operations. Space complexity is similar.

✨

Key Insights

1Insight 1: The 'pairs' array defines connected components in the string. Indices within a component can be freely swapped.
2Insight 2: Union-Find (Disjoint Set) data structure is effective for identifying connected components.
3Insight 3: Sorting the indices and characters within each component allows creating the lexicographically smallest string.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty string `s` or empty `pairs` array. The solution handles this correctly because the loops won't execute, and it will just return the original string `s` (which would be empty).
Edge case 2: `pairs` array contains duplicate pairs or self-loops (e.g., [0, 0]). The Union-Find algorithm handles these gracefully; duplicate pairs have no effect, and self-loops don't change the connected components.
Edge case 3: All indices are in a single connected component. The algorithm will still correctly sort all characters in the string.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the indices and characters within each connected component. Without sorting, the resulting string won't be lexicographically smallest.

✗Common mistake 2: Incorrectly implementing the Union-Find data structure (e.g., not using path compression or union by size), which can lead to a higher time complexity in some cases.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network connectivity analysis: determining if two computers are connected in a network through a series of connections (pairs of connected computers).

🏦Real-world scenario 2: Image processing: identifying connected regions in an image for object detection or segmentation.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 1, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Smallest String With Swaps"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?