跳转至

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

题目描述

给你一个仅由数字组成的字符串 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 仅由数字组成。

解法

方法一：贪心 + 模拟

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public String getSmallestString(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        for (int i = 1; i < n; ++i) {
            char a = cs[i - 1], b = cs[i];
            if (a > b && a % 2 == b % 2) {
                cs[i] = a;
                cs[i - 1] = b;
                return new String(cs);
            }
        }
        return s;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    string getSmallestString(string s) {
        int n = s.length();
        for (int i = 1; i < n; ++i) {
            char a = s[i - 1], b = s[i];
            if (a > b && a % 2 == b % 2) {
                s[i - 1] = b;
                s[i] = a;
                break;
            }
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func getSmallestString(s string) string {
    cs := []byte(s)
    n := len(cs)
    for i := 1; i < n; i++ {
        a, b := cs[i-1], cs[i]
        if a > b && a%2 == b%2 {
            cs[i-1], cs[i] = b, a
            return string(cs)
        }
    }
    return s
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function getSmallestString(s: string): string {
    const n = s.length;
    const cs: string[] = s.split('');
    for (let i = 1; i < n; ++i) {
        const a = cs[i - 1];
        const b = cs[i];
        if (a > b && +a % 2 === +b % 2) {
            cs[i - 1] = b;
            cs[i] = a;
            return cs.join('');
        }
    }
    return s;
}

评论