Smallest String With Swaps

Medium

Smallest String With Swaps

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the number of pairs in the `pairs` list? Are there any memory constraints I should be aware of?
Can the `pairs` list be empty? If so, what should I return?
Are the indices in the `pairs` list guaranteed to be within the bounds of the string `s` (i.e., 0 to len(s) - 1)?
If there are multiple ways to form the smallest string after swaps, is any valid solution acceptable?
Does the problem statement imply that the pairs in the `pairs` list are transitive, or should I assume that swaps are only allowed for the explicit pairs given?

Brute Force Solution

Approach

The brute force approach to finding the smallest string with swaps involves trying every single possible combination of swaps. We generate each possible string arrangement and check if it's smaller than our current smallest string. This is like trying every key on a keyring until you find the one that opens the lock.

Here's how the algorithm would work step-by-step:

Start with the original string as a potential smallest string.
Find any two positions in the string where we are allowed to swap the letters.
Swap the letters in those positions and create a new string.
Compare this new string to our current smallest string. If the new string comes earlier alphabetically, replace the current smallest string with the new string.
Repeat steps 2-4 for every possible pair of positions where swaps are allowed.
Now, consider swapping three positions, then four, and so on, until you've tried all possible combinations of swaps.
After trying every swap combination, the string we have marked as the smallest is the final answer.

Code Implementation

def smallest_string_with_swaps_brute_force(original_string, allowed_swaps):
    smallest_string = original_string

    string_length = len(original_string)
    
    # Iterate through all possible combinations of swaps
    for i in range(1 << len(allowed_swaps)):
        new_string = list(original_string)
        indices_to_swap = []

        # Determine which swaps to perform based on the binary representation of i
        for swap_index in range(len(allowed_swaps)):
            if (i >> swap_index) & 1:
                indices_to_swap.append(allowed_swaps[swap_index])

        # Apply the swaps if any swaps are selected
        if indices_to_swap:
            # Sort indices to maintain consistency
            indices_to_swap.sort()
            
            #Group characters to preserve order
            characters_to_swap = [new_string[index_pair[0]] for index_pair in indices_to_swap]
            characters_to_swap.sort()
            
            # Apply the sorted characters to the selected indices
            for char_index in range(len(indices_to_swap)):
                new_string[indices_to_swap[char_index][0]] = characters_to_swap[char_index]

        new_string = "".join(new_string)

        # Update the smallest string if the new string is smaller
        if new_string < smallest_string:
            smallest_string = new_string

    return smallest_string

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach considers all possible permutations of the string's characters reachable through the allowed swaps. In the worst-case scenario, where all characters can be swapped with each other, we have n! possible permutations of the string of length n. For each of these permutations, we must compare it to the current smallest string, which takes O(n) time. Therefore, the total time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach explores all possible string arrangements resulting from swaps. To generate all permutations of length N (where N is the length of the string), the algorithm implicitly stores all possible string permutations in memory during the recursion/iteration. Thus, in the worst-case, when trying all swaps, the space complexity grows as N! because we are essentially creating and comparing potentially all permutations of the input string. This includes potentially holding multiple string permutations in memory simultaneously for comparison to the current smallest string.

Optimal Solution

Approach

The key idea is to group together positions where letters can be swapped. Then, within each group, we want to arrange the letters in the best possible order, which is alphabetically.

Here's how the algorithm would work step-by-step:

First, figure out which positions in the string are connected to each other through the given swaps. Imagine each position as a node and each swap as a connection.
For each group of connected positions, collect all the letters from those positions.
Sort the letters you collected in each group alphabetically.
Now, put the sorted letters back into their original positions in the string, making sure to keep the order of positions from the original string.
By doing this, each connected group of letters is arranged to form the smallest possible string within that group.

Code Implementation

def smallest_string_with_swaps(input_string, pairs_of_indices):
    string_length = len(input_string)
    parent = list(range(string_length))

    def find(index):
        if parent[index] != index:
            parent[index] = find(parent[index])
        return parent[index]

    def union(index_one, index_two):
        root_one = find(index_one)
        root_two = find(index_two)
        parent[root_one] = root_two

    # Use union-find to determine connected components
    for index_one, index_two in pairs_of_indices:
        union(index_one, index_two)

    connected_components = {}
    for index in range(string_length):
        root = find(index)
        if root not in connected_components:
            connected_components[root] = []
        connected_components[root].append(index)

    result_string_list = list(input_string)

    # Sort the characters within each connected component
    for root, indices in connected_components.items():
        characters = [input_string[index] for index in indices]
        characters.sort()

        indices.sort()

        # Assign the sorted characters back to the string
        for index, character in zip(indices, characters):
            result_string_list[index] = character

    return "".join(result_string_list)

Big(O) Analysis

Time Complexity

O(n log n) – The most significant operations are grouping the swappable indices and sorting characters within each group. The grouping can be efficiently done using a Disjoint Set Union (DSU) data structure with near-constant time complexity per union and find operation, contributing close to O(n) overall. However, for each connected component (group), we extract characters and sort them. In the worst case, all indices belong to a single group, leading to extracting n characters and then sorting them in O(n log n) time. Since the connected components are disjoint, the sorting across all components is bounded by O(n log n). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm uses a Disjoint Set Union (DSU) data structure (implicitly described as 'grouping positions') which can take up O(N) space where N is the length of the string. Also, for each connected group, the algorithm collects letters into a temporary list, and stores the positions of those letters in another list; in the worst case, all letters belong to one group, leading to O(N) space for each of these lists. Finally, sorting the collected letters requires additional space; common sorting algorithms, in-place or otherwise, may use up to O(N) space. The dominant space usage comes from storing the DSU structure and the temporary lists, resulting in O(N) auxiliary space overall.

Edge Cases

Case	How to Handle
Null or empty string s	Return an empty string or throw an exception if input string s is null or empty.
Null or empty pairs list	Return the original string if the pairs list is null or empty, as no swaps are specified.
String s has length 1	Return the original string as no swaps can change the string.
Pairs list contains invalid indices (out of string bounds)	Ignore the invalid pair or throw an exception to prevent array out-of-bounds errors.
Pairs list contains duplicate pairs	The union-find data structure handles this as redundant pairs are merged in the same connected component.
Pairs form cycles in the string indices	The union-find approach correctly identifies connected components even when they contain cycles.
All characters in the string are the same	The algorithm should still correctly group the indices and sort the corresponding characters within the connected components.
Very long string and very large pairs list exceeding memory limits	Consider using an iterative depth-first search instead of recursion in the union-find algorithm to avoid stack overflow and optimize memory usage.