[LeetCode] 3216. Lexicographically Smallest String After a Swap

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 <= 100
s consists only of digits.

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

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

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

思路

注意交换的规则，两个数字只能同为奇数或者同为偶数才能互相交换。所以思路是从左往右遍历所有的字符，如果某两个相邻的字符 a 和 b (a 在左，b 在右) 具有相同的奇偶性且 a > b，则可以进行交换。照着这个思路，找到第一对符合条件的 a 和 b，即可交换并返回结果。为什么是第一对，是因为需要让字典序尽可能的小，你交换在后面的字符，字典序是不如交换第一对大的。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String getSmallestString(String s) {
        int n = s.length();
        char[] letters = s.toCharArray();
        for (int i = 1; i < n; i++) {
            int a = letters[i - 1] - '0';
            int b = letters[i] - '0';
            if (helper(a, b) && a > b) {
                char temp = letters[i - 1];
                letters[i - 1] = letters[i];
                letters[i] = temp;
                return new String(letters);
            }
        }
        return s;
    }

    private boolean helper(int a, int b) {
        return a % 2 == b % 2;
    }
}