Problem Description

You are given a string s that contains only digits. Your task is to find the lexicographically smallest string possible by swapping adjacent digits that have the same parity, but you can perform this swap at most once.

Two digits have the same parity when:

• Both digits are odd (like 1, 3, 5, 7, 9)
• Both digits are even (like 0, 2, 4, 6, 8)

For example:

• Digits 5 and 9 have the same parity (both odd)
• Digits 2 and 4 have the same parity (both even)
• Digits 6 and 9 have different parity (6 is even, 9 is odd)

You can only swap two digits if they are:

1. Adjacent to each other in the string
2. Have the same parity
3. You haven't already performed a swap (maximum one swap allowed)

The goal is to make the resulting string as small as possible in lexicographical order. In lexicographical ordering, a string is smaller if it would appear earlier in a dictionary. For example, "123" is lexicographically smaller than "132".

If no beneficial swap can be made, return the original string.

Intuition

To get the lexicographically smallest string, we want smaller digits to appear as early as possible in the string. Since we can only swap adjacent digits with the same parity once, we need to make this single swap count.

The key insight is that we should perform the swap at the first opportunity where it would improve the string's lexicographical order. Why? Because moving a smaller digit earlier in the string has more impact on the lexicographical ordering than moving it later.

Consider scanning the string from left to right. When we encounter two adjacent digits with the same parity, we check if swapping them would make the string smaller. This happens when the left digit is larger than the right digit. For example, if we have "42", swapping gives us "24", which is lexicographically smaller.

The greedy approach works here because:

1. We want to fix the leftmost position possible with a smaller digit
2. Once we find the first beneficial swap, we should take it immediately
3. Any swap opportunity we skip might never give us as much benefit as fixing an earlier position

For instance, if we have "531", we can swap positions 0-1 to get "351" (both 5 and 3 are odd). Even if there were other valid swaps later in a longer string, fixing position 0 with a smaller digit gives us the best lexicographical improvement.

This leads us to a simple algorithm: traverse the string once, find the first pair of adjacent same-parity digits where the left is greater than the right, swap them, and return. If no such pair exists, the string is already optimal.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy simulation approach by traversing the string from left to right and checking each pair of adjacent digits.

The algorithm works as follows:

1. Iterate through adjacent pairs: We traverse the string using pairwise(map(ord, s)) which gives us pairs of adjacent characters converted to their ASCII values. The pairwise function creates pairs like (s[0], s[1]), (s[1], s[2]), and so on.

2. Check parity condition: For each pair (a, b), we check if they have the same parity using (a + b) % 2 == 0. This clever trick works because:

   • If both digits are odd, their ASCII values are odd, so odd + odd = even, and even % 2 = 0
   • If both digits are even, their ASCII values are even, so even + even = even, and even % 2 = 0
   • If one is odd and one is even, odd + even = odd, and odd % 2 = 1

3. Check if swap is beneficial: We verify if a > b, meaning the left digit is greater than the right digit. Swapping in this case would move the smaller digit to an earlier position, making the string lexicographically smaller.

4. Perform the swap: If both conditions are met, we reconstruct the string by:

   • Taking the substring from start to position i: s[:i]
   • Adding the swapped digits: s[i + 1] + s[i]
   • Appending the rest of the string: s[i + 2:]
   • This effectively swaps the digits at positions i and i + 1

5. Return immediately: Once we find and perform the first beneficial swap, we return the modified string immediately, as we can only swap once and want the earliest possible improvement.

6. No swap needed: If we complete the iteration without finding any swappable pair, we return the original string s as it's already in its optimal form.

The time complexity is O(n) where n is the length of the string, as we traverse it at most once. The space complexity is O(n) for creating the result string.

Example Walkthrough

Let's walk through the solution with the example string s = "45320".

Step 1: Initialize and start iteration

• We begin traversing adjacent pairs from left to right
• Convert each character to its ASCII value for easier parity checking

Step 2: Check first pair (4, 5) at positions 0-1

• ASCII values: 4 → 52, 5 → 53
• Check parity: (52 + 53) % 2 = 105 % 2 = 1 (different parity)
• Since they have different parity, we cannot swap them
• Continue to next pair

Step 3: Check second pair (5, 3) at positions 1-2

• ASCII values: 5 → 53, 3 → 51
• Check parity: (53 + 51) % 2 = 104 % 2 = 0 (same parity - both odd)
• Check if beneficial: 5 > 3? Yes!
• This is our first opportunity for a beneficial swap

Step 4: Perform the swap

• Original: "45320"
• Swap positions 1 and 2:
  • Take substring before position 1: "4"
  • Add swapped digits: "3" + "5" = "35"
  • Add remaining substring: "20"
• Result: "4" + "35" + "20" = "43520"

Step 5: Return immediately

• We've used our one allowed swap
• Return "43520"

The string "43520" is lexicographically smaller than "45320" because at position 1, '3' < '5'. Even though there might be other swappable pairs later (like positions 3-4 with digits 2 and 0, both even), we take the first beneficial swap because fixing an earlier position gives us the best lexicographical improvement.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string once using pairwise, checking each adjacent pair of characters. In the worst case, it examines all n-1 pairs before either finding a swap or returning the original string.

The space complexity is O(n), where n is the length of the string s. Although the pairwise iterator and map function create lazy iterators that don't consume extra space proportional to input size, the string slicing operations (s[:i] + s[i + 1] + s[i] + s[i + 2:]) create a new string when a swap is performed. Since strings are immutable in Python, this concatenation creates a new string of length n, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting Multiple Swaps Instead of Just One

A common mistake is trying to perform multiple swaps to get an even smaller string. The problem explicitly states we can swap at most once, but developers might accidentally continue swapping after finding the first beneficial swap.

Incorrect approach:

def getSmallestString(self, s: str) -> str:
    chars = list(s)
    for i in range(len(chars) - 1):
        if (ord(chars[i]) + ord(chars[i + 1])) % 2 == 0:
            if chars[i] > chars[i + 1]:
                # Wrong: modifying chars and continuing the loop
                chars[i], chars[i + 1] = chars[i + 1], chars[i]
    return ''.join(chars)

Why it's wrong: This continues iterating and potentially swapping multiple times. For example, with input "7319", this would swap to "3719" then to "3179", performing two swaps instead of one.

Correct approach: Return immediately after the first swap:

def getSmallestString(self, s: str) -> str:
    for i in range(len(s) - 1):
        if (ord(s[i]) + ord(s[i + 1])) % 2 == 0:
            if ord(s[i]) > ord(s[i + 1]):
                # Return immediately after first swap
                return s[:i] + s[i + 1] + s[i] + s[i + 2:]
    return s

2. Incorrect Parity Check Using Digit Values Instead of ASCII Values

Some developers might check parity using the actual digit values rather than working with ASCII values or characters directly.

Incorrect approach:

def getSmallestString(self, s: str) -> str:
    for i in range(len(s) - 1):
        digit1 = int(s[i])
        digit2 = int(s[i + 1])
        # This works but adds unnecessary conversion overhead
        if digit1 % 2 == digit2 % 2:  
            if digit1 > digit2:
                return s[:i] + s[i + 1] + s[i] + s[i + 2:]
    return s

Why it's suboptimal: While this works correctly, it performs unnecessary int conversions. The ASCII values of digits preserve the same parity as the digits themselves (e.g., '0' has ASCII 48 which is even, '1' has ASCII 49 which is odd).

Better approach: Use ASCII values or character comparison directly:

# Using ASCII values (more efficient)
if (ord(s[i]) + ord(s[i + 1])) % 2 == 0:
    if s[i] > s[i + 1]:  # Character comparison works for digits
        return s[:i] + s[i + 1] + s[i] + s[i + 2:]

3. Not Considering the Greedy Nature of the Problem

Some might think they need to check all possible swaps and choose the best one, leading to unnecessary complexity.

Incorrect approach:

def getSmallestString(self, s: str) -> str:
    best = s
    for i in range(len(s) - 1):
        if (ord(s[i]) + ord(s[i + 1])) % 2 == 0:
            if s[i] > s[i + 1]:
                swapped = s[:i] + s[i + 1] + s[i] + s[i + 2:]
                if swapped < best:
                    best = swapped
    return best

Why it's wrong: This tries to find the "best" swap among all possibilities, but since we traverse left to right and want the lexicographically smallest result, the first beneficial swap we encounter is always the optimal choice. Any swap further to the right affects less significant positions.

Correct greedy approach: Take the first beneficial swap:

for i in range(len(s) - 1):
    if (ord(s[i]) + ord(s[i + 1])) % 2 == 0 and s[i] > s[i + 1]:
        return s[:i] + s[i + 1] + s[i] + s[i + 2:]
return s