#3216

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Lexicographically Smallest String After a Swap

Lexicographically Smallest String After a Swap involves finding the smallest string after swapping adjacent digits with the same parity.

string greedy

Problem Statement

You are given a string s consisting only of digits. Your goal is to determine the lexicographically smallest string that can be obtained by swapping at most once any two adjacent digits that have the same parity.

A digit pair has the same parity if both are odd or both are even. For example, digits '5' and '9' have the same parity, as do '2' and '4'. However, '6' and '9' do not have the same parity. You need to return the smallest possible string after applying the valid swap.

Examples

Example 1

Input: s = "45320"

Output: "43520"

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"

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 Approach

Greedy Swap Evaluation

This solution follows a greedy approach where you evaluate each adjacent pair of digits with the same parity. If a swap would lead to a smaller lexicographical string, execute the swap and finalize the string. This approach ensures the lexicographically smallest string by always opting for the most beneficial swap.

Checking Parity Matching

To identify potential swaps, iterate through the string and check for adjacent digits that have the same parity (either both odd or both even). Only consider swaps between such pairs to maintain the problem's constraints and keep the solution efficient.

Efficient Swapping Logic

Once a pair of digits with the same parity is identified, swap them if it results in a smaller string. After swapping, the process stops since only one swap is allowed. This guarantees that the final string is the lexicographically smallest.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the approach used to evaluate and swap digits. If all adjacent pairs are checked, the complexity would be O(n), where n is the length of the string. The space complexity is O(1) as only a few variables are used to track the string and swap status.

What Interviewers Usually Probe

Is the candidate able to recognize and apply the greedy approach for optimal string minimization?
Can the candidate effectively check for parity conditions before performing swaps?
Does the candidate manage string mutations efficiently with the given constraints?

Common Pitfalls or Variants

Common pitfalls

Candidates may overlook the need to check both parity matching and the lexicographical order after swaps.
A common mistake is performing unnecessary swaps or trying multiple swaps, which violates the problem's constraints.
Not handling edge cases where no swap is needed (e.g., a string that's already the lexicographically smallest).

Follow-up variants

Handling strings of varying lengths, from the minimum size to larger inputs, to ensure the algorithm scales.
Introducing additional constraints, such as limiting the number of swaps, or requiring swaps only in specific positions.
Changing the allowed parity matching condition (e.g., only odd digits or only even digits can be swapped).

FAQ

What is the lexicographically smallest string after a swap?

The lexicographically smallest string is the string that would come first if all possible strings were sorted in dictionary order. This can be achieved by swapping adjacent digits with the same parity.

How do I determine if two digits have the same parity?

Two digits have the same parity if both are either even or both are odd. For example, '4' and '2' are both even, and '5' and '9' are both odd.

What is a greedy approach in this problem?

A greedy approach involves choosing the best possible swap at each step. In this case, you always choose to swap two adjacent digits with the same parity if it results in a lexicographically smaller string.

What happens if there is no possible swap?

If no adjacent digits with the same parity can be swapped, the string remains unchanged, and the problem is solved without any modifications.

Can this problem be solved in less than O(n) time?

No, as you must check each adjacent pair of digits to determine if a swap is valid, meaning the problem requires at least O(n) time to evaluate all possible swaps.

terminal

Solution

Solution 1: Greedy + Simulation

We can traverse the string $\textit{s}$ from left to right. For each pair of adjacent digits, if they have the same parity and the previous digit is greater than the next digit, then we swap these two digits to make the lexicographical order of the string $\textit{s}$ smaller, and then return the swapped string.

1

2

3

4

5

6

class Solution:
    def getSmallestString(self, s: str) -> str:
        for i, (a, b) in enumerate(pairwise(map(ord, s))):
            if (a + b) % 2 == 0 and a > b:
                return s[:i] + s[i + 1] + s[i] + s[i + 2 :]
        return s

Continue Practicing

#3228 maximum number of operations to move ones to the end #3260 find the largest palindrome divisible by k #3170 lexicographically minimum string after removing stars