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 <= 100s consists only of digits.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:
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:
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_foundSorting 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:
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)| Case | How to Handle |
|---|---|
| The digits are already sorted | Return the original text, because it matches the sorted order and no swap is required. |
| All digits are equal | 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 | 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 | That swap is the smallest result and is selected over every other pair. |
| The direct search generates every pair of positions | Include the untouched string with those swapped copies and return the minimum. |