Smallest String With Swaps

TIP103 Unit 7 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Graphs, Union-Find (Disjoint Set), Connected Components, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: Can we use each pair more than once?

  • A: Yes, we may swap the characters at a pair's two indices as many times as we like.

• Q: What does unlimited swapping let us do?

  • A: If indices are connected through a chain of pairs, the characters at those indices can be rearranged into any order. So the indices form groups (connected components), and within each group we can freely permute characters.

• Q: What if pairs is empty?

  • A: No swaps are possible, so we return s unchanged.

HAPPY CASE
Input: s = "dcab", pairs = [[0, 3], [1, 2]]
Output: "bacd"
Explanation: Indices {0, 3} form one group and {1, 2} form another. Swap indices 0 and 3 to get "bcad", then swap indices 1 and 2 to get "bacd".

Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]]
Output: "abcd"
Explanation: The pair [0, 2] links the two groups into one component {0, 1, 2, 3}, so all four characters can be freely rearranged into sorted order.

EDGE CASE
Input: s = "cba", pairs = []
Output: "cba"
Explanation: With no pairs, no swaps are possible, so the string stays unchanged.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Connectivity / Grouping Problems, we can consider the following approaches:

• Union-Find (Disjoint Set): Union the two indices of every pair so that all mutually swappable indices share one root. This is the approach the problem asks for.
• DFS (Depth-First Search): Alternatively, build an adjacency list from the pairs and DFS to find connected components of indices.

The key insight is that unlimited swaps within a connected component let us sort the characters of that component independently.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Treat each index of the string as a node and each pair as an edge. Use Union-Find to group indices into connected components. Within each component, collect the characters, sort them, and write them back onto the component's indices in sorted index order. This greedily places the smallest available character at the smallest available index, producing the lexicographically smallest string.

1) Initialize a `parent` array where each index is its own parent.
2) Define `find(x)` to return the root of `x` (with path compression) and `union(x, y)` to merge two roots.
3) For each pair (a, b) in `pairs`, call `union(a, b)`.
4) Group all indices by their root into a dictionary: root -> list of indices.
5) For each group:
   a) Collect the characters at the group's indices and sort them.
   b) Sort the group's indices.
   c) Assign the sorted characters to the sorted indices, smallest character to smallest index.
6) Join and return the resulting characters as a string.

⚠️ Common Mistakes

• Only applying each pair once instead of realizing unlimited swaps make a whole component freely permutable.
• Sorting the characters but forgetting to also sort the indices, so characters land at the wrong positions.
• Skipping path compression (or union by rank), which can make Union-Find degrade toward linear-time finds on long chains.
• Trying to mutate the string directly instead of converting it to a list of characters first.

4: I-mplement

Implement the code to solve the algorithm.

def smallest_string_with_swaps(s, pairs):
    n = len(s)
    parent = list(range(n))

    def find(x):
        # Path compression: point x toward the root of its group
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y

    # 1) Union the two indices of every pair
    for a, b in pairs:
        union(a, b)

    # 2) Group indices by their root (connected component)
    groups = {}
    for i in range(n):
        root = find(i)
        groups.setdefault(root, []).append(i)

    # 3) Within each group, sort the characters and place them
    #    onto the group's indices in sorted order
    result = list(s)
    for indices in groups.values():
        chars = sorted(result[i] for i in indices)
        for i, ch in zip(sorted(indices), chars):
            result[i] = ch

    return "".join(result)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • Union(0, 3) and Union(1, 2) produce two components: {0, 3} and {1, 2}.
  • Component {0, 3} holds characters ['d', 'b'] → sorted ['b', 'd'] → index 0 gets 'b', index 3 gets 'd'.
  • Component {1, 2} holds characters ['c', 'a'] → sorted ['a', 'c'] → index 1 gets 'a', index 2 gets 'c'.
  • Output: "bacd"

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

  • Union(0, 2) merges the two components into one: {0, 1, 2, 3}.
  • The component holds all characters ['d', 'c', 'a', 'b'] → sorted ['a', 'b', 'c', 'd'] placed at indices 0-3.
  • Output: "abcd"

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

  • Every index is its own component, so nothing moves.
  • Output: "cba"

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the string and P is the number of pairs.

• Time Complexity: O((N + P) α(N) + N log N), where α is the near-constant inverse Ackermann factor from Union-Find. The unions cost O(P α(N)), grouping the indices costs O(N α(N)), and sorting the characters and indices across all groups costs O(N log N) total, which dominates in practice.
• Space Complexity: O(N) for the parent array, the groups dictionary, and the result character list.