Taro Logo

Lexicographically Smallest String After a Swap

Easy
Asked by:
Profile picture
6 views
Topics:
StringsGreedy Algorithms

Given a string s containing only digits, return the lexicographically smallest string that can be obtained after swapping adjacent digits in s with the same parity at most once.

Digits have the same parity if both are odd or both are even. For example, 5 and 9, as well as 2 and 4, have the same parity, while 6 and 9 do not.

Example 1:

Input: s = "45320"

Output: "43520"

Explanation:

s[1] == '5' and s[2] == '3' both have the same parity, and swapping them results in the lexicographically smallest string.

Example 2:

Input: s = "001"

Output: "001"

Explanation:

There is no need to perform a swap because s is already the lexicographically smallest.

Constraints:

  • 2 <= s.length <= 100
  • s consists only of digits.

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:

  1. Is at most one swap allowed, including the choice to leave the text unchanged?
  2. May the swapped positions be any pair, rather than only neighboring digits?
  3. Are the characters digits compared in ordinary left-to-right dictionary order?
  4. Should the original text be kept when every swap makes it larger?
  5. If several one-swap results are equal, is any copy of that smallest text acceptable?

Brute Force Solution

Approach

This search builds the original string and every string that can be made by swapping one pair of positions. The pair can be any two indexes, not only neighbors. The smallest string in that collection is the answer, which also covers doing no swap.

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

  1. Put the original text into the list of candidates.
  2. Choose every first index from the left.
  3. Choose every second index strictly to the right of the first.
  4. Copy the digits, swap the two chosen positions, and append the new string.
  5. After every pair has been generated, select the minimum string in the list.
  6. Return that minimum, which is the original when no swap improves it.

Code Implementation

def lexicographically_smallest_brute_force(original_string_of_numbers):
    number_of_digits = len(original_string_of_numbers)
    list_of_possible_strings = [original_string_of_numbers]

    # We need to generate all possible strings that can be formed by a single swap.
    for first_index in range(number_of_digits):
        for second_index in range(first_index + 1, number_of_digits):
            list_of_digits = list(original_string_of_numbers)

            # Perform the swap to create a new potential candidate string.
            list_of_digits[first_index], list_of_digits[second_index] = list_of_digits[second_index], list_of_digits[first_index]
            
            newly_swapped_string = "".join(list_of_digits)
            list_of_possible_strings.append(newly_swapped_string)

    # The original string is already included, covering the case where no swap is made.
    smallest_string_found = min(list_of_possible_strings)

    # After generating all outcomes, we simply find the lexicographically smallest one.
    return smallest_string_found

Big(O) Analysis

Time Complexity
O(n^3) – The number of unordered pairs of positions in a string of length n is about n squared over two. Building the swapped copy of one pair copies n characters, which already costs cubic work. Finding the minimum then compares those n squared strings, and each comparison can look at n characters. The comparisons are the same cubic order as the copying. The total is O(n^3).
Space Complexity
O(n^3) – Every pair produces its own string, and there are a quadratic number of pairs plus the original. Each stored string contains n characters. Multiplying a quadratic count by a linear length gives cubic storage. The scan that finds the minimum does not allocate another full set of strings. Extra space is O(n^3).

Optimal Solution

Approach

Sorting a copy reveals the first position that is not already in sorted order. The digit that belongs in that position is taken from the sorted copy, and it is swapped with the rightmost occurrence of that same digit in the working copy. If the text is already sorted, it is returned unchanged.

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

  1. Copy the digits into a mutable list and sort a second copy.
  2. Scan from the left for the first position where the two copies differ.
  3. If there is no such position, join the mutable list and return it.
  4. Read the digit that the sorted copy holds at the mismatch.
  5. Scan from the right for the last occurrence of that digit in the mutable list.
  6. Swap it with the mismatch position.
  7. Join the mutable list and return it.

Code Implementation

def get_smallest_string(input_string):
    string_as_list = list(input_string)
    sorted_string_list = sorted(string_as_list)

    # Find the first character that is not in its ideal sorted position.
    first_mismatch_index = -1
    for current_index in range(len(string_as_list)):
        if string_as_list[current_index] != sorted_string_list[current_index]:
            first_mismatch_index = current_index
            break

    # If the string is already sorted, no swap can make it smaller.
    if first_mismatch_index == -1:
        return "".join(string_as_list)

    character_to_swap = sorted_string_list[first_mismatch_index]

    # The best swap is with the smallest character that should be at the mismatch position.
    for index_from_right in range(len(string_as_list) - 1, -1, -1):
        if string_as_list[index_from_right] == character_to_swap:
            # Swap the out-of-place character with the rightmost occurrence of the smallest char.
            string_as_list[first_mismatch_index], string_as_list[index_from_right] = \
                string_as_list[index_from_right], string_as_list[first_mismatch_index]
            break

    return "".join(string_as_list)

Big(O) Analysis

Time Complexity
O(n log n) – Sorting the copied digits dominates the work and takes O(n log n) comparisons. The scan for the first mismatch looks at each position at most once. The scan from the right also looks at each position at most once and stops at the chosen digit. The swap and the final join are linear. The sort is the slowest step, so the bound is O(n log n).
Space Complexity
O(n) – Two lists of digits are stored, the working copy and the sorted copy, and each has length n. The scans use a constant number of indexes. No table of other swaps is allocated. The returned string is the output. Extra space is O(n).

Edge Cases

The digits are already sorted
How to Handle:
Return the original text, because it matches the sorted order and no swap is required.
All digits are equal
How to Handle:
Return the original text, because every swap leaves the same characters in place.
The first digit is already the smallest, but a later digit is out of order
How to Handle:
Leave the matching prefix alone and swap the earliest wrong digit with the rightmost copy of the digit that belongs there.
One swap can fully sort the digits
How to Handle:
That swap is the smallest result and is selected over every other pair.
The direct search generates every pair of positions
How to Handle:
Include the untouched string with those swapped copies and return the minimum.