LeetCode 3216 - Lexicographically Smallest String After a Swap
The problem requires transforming a string of digits into its lexicographically smallest form by performing at most one swap between adjacent digits of the same parity. Here, parity refers to whether a digit is even or odd.
Difficulty: 🟢 Easy
Topics: String, Greedy
Solution
Problem Understanding
The problem requires transforming a string of digits into its lexicographically smallest form by performing at most one swap between adjacent digits of the same parity. Here, parity refers to whether a digit is even or odd. Two digits can only be swapped if both are odd or both are even.
The input is a string s with length between 2 and 100, containing only digit characters '0' to '9'. The expected output is a string of the same length that represents the smallest lexicographic ordering achievable under the described constraints.
The key aspects are understanding lexicographical order (similar to dictionary order), recognizing parity for swapping, and noting that only adjacent swaps are allowed, and only once per swap opportunity. Edge cases include strings where all swaps would not improve the order, strings with repeated digits, and strings where parity constraints prevent any beneficial swap.
Approaches
A brute-force approach would consider all possible pairs of adjacent digits with the same parity, swap each pair, and then compare the resulting strings to select the lexicographically smallest one. While correct, this approach is inefficient because it would iterate over all adjacent parity pairs and create new strings for comparison, yielding a time complexity of O(n) swaps, each involving O(n) string comparison, which is acceptable for small n but unnecessary given a more greedy approach.
The key observation is that to achieve the lexicographically smallest string, one only needs to consider swapping each adjacent pair of the same parity if it decreases the string lexicographically, starting from the left. This is a greedy approach because the leftmost digits have the largest impact on lexicographic ordering. By scanning from left to right and performing the first beneficial swap, we ensure minimal string without needing to try all possibilities.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Swap every valid adjacent pair and compare all resulting strings |
| Optimal | O(n) | O(n) | Scan left to right, swap first beneficial adjacent parity pair |
Algorithm Walkthrough
- Convert the string
sinto a list of characters for easy swapping. - Iterate through the string from index 0 to
len(s) - 2. - For each index
i, check ifs[i]ands[i+1]have the same parity. This is done by converting the characters to integers and checking modulo 2. - If they have the same parity and
s[i] > s[i+1], perform the swap. This ensures the leftmost digit is as small as possible. - Stop iterating after the first swap because only one swap per opportunity is allowed. Return the modified string.
Why it works: Swapping leftmost digits that are out of order (within parity constraints) ensures the largest lexicographical gain. Any later swap would not produce a smaller string because the leftmost characters dominate lexicographic order.
Python Solution
class Solution:
def getSmallestString(self, s: str) -> str:
chars = list(s)
for i in range(len(chars) - 1):
if (int(chars[i]) % 2) == (int(chars[i+1]) % 2) and chars[i] > chars[i+1]:
chars[i], chars[i+1] = chars[i+1], chars[i]
break
return ''.join(chars)
The Python implementation converts the string into a list to allow easy swapping. It then iterates left to right, checking parity and lexicographic order. The first beneficial swap is executed and the loop is broken. The list is joined back into a string for the final output.
Go Solution
func getSmallestString(s string) string {
chars := []rune(s)
for i := 0; i < len(chars)-1; i++ {
a := chars[i] - '0'
b := chars[i+1] - '0'
if a%2 == b%2 && chars[i] > chars[i+1] {
chars[i], chars[i+1] = chars[i+1], chars[i]
break
}
}
return string(chars)
}
In Go, we convert the string to a slice of runes for mutable operations. Subtracting '0' gives integer values for parity checks. The first beneficial swap is executed and the result is converted back to a string.
Worked Examples
Example 1: s = "45320"
| i | chars | Swap? | Result |
|---|---|---|---|
| 0 | 4,5,3,2,0 | 4 and 5: different parity | No |
| 1 | 4,5,3,2,0 | 5 and 3: same parity (odd) and 5>3 | Yes |
Output: "43520"
Example 2: s = "001"
| i | chars | Swap? | Result |
|---|---|---|---|
| 0 | 0,0,1 | 0 and 0: same parity but 0 not > 0 | No |
| 1 | 0,0,1 | 0 and 1: different parity | No |
Output: "001"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We iterate through the string once, performing at most one swap. |
| Space | O(n) | We convert the string to a mutable list of characters. |
The reasoning is that we only perform a single linear pass over the input. No nested loops or additional data structures are needed beyond the mutable character list.
Test Cases
# Basic examples
assert Solution().getSmallestString("45320") == "43520" # swap 5 and 3
assert Solution().getSmallestString("001") == "001" # no swap needed
# Edge cases
assert Solution().getSmallestString("22") == "22" # two even digits, already ordered
assert Solution().getSmallestString("21") == "21" # different parity, cannot swap
assert Solution().getSmallestString("9876543210") == "8976543210" # first odd swap
assert Solution().getSmallestString("11111") == "11111" # all odd, all same
assert Solution().getSmallestString("8642") == "6842" # first even swap
| Test | Why |
|---|---|
| "45320" | Normal case with one odd swap |
| "001" | No swap improves string |
| "22" | Already sorted even digits |
| "21" | Different parity, swap not allowed |
| "9876543210" | First beneficial odd swap |
| "11111" | All same parity and digits, no change |
| "8642" | First beneficial even swap |
Edge Cases
Case 1: All digits have the same parity. A string like "2468" may require swaps to reorder digits. Our algorithm handles this because it scans left to right and swaps the first out-of-order adjacent pair.
Case 2: No beneficial swaps exist. For a string like "001" or "123", no swap improves lexicographic order. The implementation correctly iterates through the string and returns the original string unmodified.
Case 3: Repeated digits. For a string like "11122", swaps among repeated digits should not change the string. The parity check and > comparison prevent unnecessary swaps, ensuring correctness.
This solution is efficient, simple, and directly implements the greedy observation to guarantee the lexicographically smallest string under the constraints.