Smallest String With Swaps - Practice Coding Problems

Smallest String With Swaps - Problem

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

You are given a string s and an array of pairs of indices 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.

Input & Output

Example 1 — Basic Swapping

$ Input: s = "dcba", pairs = [[0,3],[1,2]]

› Output: "abcd"

💡 Note: Position 0 can swap with 3 (d↔a), position 1 can swap with 2 (c↔b). Optimal arrangement: a,b,c,d gives "abcd"

Example 2 — Transitive Connections

$ Input: s = "dcba", pairs = [[0,3],[1,2],[0,2]]

› Output: "abcd"

💡 Note: All positions are connected transitively: 0↔3, 1↔2, 0↔2 means all can swap. Sort all chars: [a,b,c,d] gives "abcd"

Example 3 — No Swaps Possible

$ Input: s = "cba", pairs = []

› Output: "cba"

💡 Note: No pairs given, so no swaps are allowed. String remains unchanged: "cba"

Constraints

1 ≤ s.length ≤ 10⁵
0 ≤ pairs.length ≤ 10⁵
0 ≤ pairs[i][0], pairs[i][1] < s.length
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with allowed swap pairs

Group Connections

Find transitively connected positions

Sort Within Groups

Arrange characters optimally in each group

Key Takeaway

🎯 Key Insight: Group transitively connected positions and sort characters within each group for optimal lexicographic arrangement

Asked in

A Amazon 15 G Google 12 F Facebook 8 M Microsoft 6

The key insight is recognizing that if positions can swap transitively (A↔B, B↔C means A↔C), we can group them and sort their characters optimally. Best approach uses Union-Find to efficiently group connected positions, then sort characters within each group. Time: O(n log n + m α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(n² × m)	O(n)	Keep swapping characters until no more improvements possible
DFS Connected Components	O(n + m + n log n)	O(n + m)	Use DFS to find connected components of swappable positions, then sort within each component
Union-Find (Disjoint Set Union)	O(n log n + m α(n))	O(n)	Group connected positions using Union-Find, then sort characters within each group

Brute Force - Try All Swaps — Algorithm Steps

Convert string to character array
Repeat: check all pairs for beneficial swaps
If any swap improves lexicographic order, perform it
Stop when no improvements possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial

Start with original string

Check Pairs

Look for pairs where left > right character

Swap & Repeat

Swap beneficial pairs, repeat until no changes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* solution(char* s, int pairs[][2], int pairsSize) {
    int n = strlen(s);
    char* result = malloc((n + 1) * sizeof(char));
    strcpy(result, s);
    
    // Keep swapping until no improvement
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < pairsSize; i++) {
            int a = pairs[i][0], b = pairs[i][1];
            if (result[a] > result[b]) {
                char temp = result[a];
                result[a] = result[b];
                result[b] = temp;
                changed = true;
            }
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    // Simple parsing for pairs - assumes format [[a,b],[c,d]]
    int pairs[1000][2];
    int pairsSize = 0;
    
    char pairsLine[10000];
    fgets(pairsLine, sizeof(pairsLine), stdin);
    
    // Basic parsing
    char* ptr = pairsLine;
    while (*ptr) {
        if (*ptr == '[') {
            ptr++;
            if (sscanf(ptr, "%d,%d", &pairs[pairsSize][0], &pairs[pairsSize][1]) == 2) {
                pairsSize++;
            }
        }
        ptr++;
    }
    
    char* result = solution(s, pairs, pairsSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

May need O(n) iterations, each checking O(m) pairs and O(n) string comparison

⚠ Quadratic Growth

Space Complexity

O(n)

Character array copy of the string

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler