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.

#3216

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

交换后字典序最小的字符串

给你一个仅由数字组成的字符串 s ，在最多交换一次相邻且具有相同奇偶性的数字后，返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。示例 1：输入： s = "45320" …

字符串贪心

题目描述

给你一个仅由数字组成的字符串 s，在最多交换一次相邻且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。

如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。

示例 1：

输入： s = "45320"

输出： "43520"

解释：

s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。

示例 2：

输入： s = "001"

输出： "001"

解释：

无需进行交换，因为 s 已经是字典序最小的。

提示：

2 <= s.length <= 100
s 仅由数字组成。

lightbulb

解题思路

方法一：贪心 + 模拟

我们可以从左到右遍历字符串 $\textit{s}$ ，对于每一对相邻的数字，如果它们具有相同的奇偶性且前一个数字大于后一个数字，那么我们就交换这两个数字，使得字符串 $\textit{s}$ 的字典序变小，然后返回交换后的字符串。

遍历结束后，如果没有找到可以交换的数字对，说明字符串 $\textit{s}$ 已经是字典序最小的，直接返回即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $\textit{s}$ 的长度。

1

2

3

4

5

6

7

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3228 将 1 移动到末尾的最大操作次数 #3260 找出最大的 N 位 K 回文数 #3170 删除星号以后字典序最小的字符串