2663-字典序最小的美丽字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

如果一个字符串满足以下条件，则称其为 美丽字符串 ：

  • 它由英语小写字母表的前 k 个字母组成。
  • 它不包含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。

请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s
的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a
的字典序大于字符串 b 。

  • 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

示例 1：

**输入：** s = "abcz", k = 26
**输出：** "abda"
**解释：** 字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。
可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

**输入：** s = "dc", k = 4
**输出：** ""
**解释：** 可以证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

提示：

  • 1 <= n == s.length <= 105
  • 4 <= k <= 26
  • s 是一个美丽字符串

本题视频讲解

见【力扣周赛 343】 第四题。

提示 1

长度为 m 的回文串必然包含长度为 m-2 的回文串。

所以只需要保证答案不包含长度为 2 或者长度为 3 的回文串。

换句话说，不能出现 s[i]=s[i-1] 以及 s[i]=s[i-2]。

这个性质十分重要，它意味着我们只需要判断 s[i] 左侧的两个字母。

s[i] 与其右边的两个字母 s[i+1] 和 s[i+2] 呢？交给 i+1 和 i+2 来判断。

提示 2

既然要字典序最小，那么修改的位置越靠右越好。

下面把 s 看成一个 k 进制数来理解。也就是说，a' 视作 0，b’ 视作 1，依此类推。

例如 s=\text{dacd，先把末尾的 s[3]=\text{d 加一，进位得到 dada。但这样前三个字母和后三个字母都形成了回文串，我们先来解决前面的，也就是把 s[2]=\text{d 加一，进位得到 dbaa，这样前面没有回文串了。反过来检查后面是否有回文串，把 s[3]=\text{a 加一，得到 dbab，还是有回文串，再把 s[3]=\text{b 加一，得到 dbac，这样就没有回文串了。由于输入的 s 本来就不包含回文串，所以更前面的字符就无需检查了，直接返回答案。

如果计算过程中出现把 s[0] 加一后不在前 k 个字母中的情况，说明答案不存在，返回空字符串。

注：上面的描述中并没有用到 k\ge 4 这个条件。更多相关讨论见视频讲解。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        a = ord('a')
        k += a
        s = list(map(ord, s))
        n = len(s)
        i = n - 1
        s[i] += 1  # 从最后一个字母开始
        while i < n:
            if s[i] == k:  # 超过范围
                if i == 0: return ""  # 无法进位
                # 进位
                s[i] = a
                i -= 1
                s[i] += 1
            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
                s[i] += 1  # 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
            else:
                i += 1  # 检查 s[i] 是否和后面的字符形成回文串
        return ''.join(map(chr, s))
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String smallestBeautifulString(String S, int k) {
        k += 'a';
        var s = S.toCharArray();
        int n = s.length, i = n - 1;
        ++s[i]; // 从最后一个字母开始
        while (i < n) {
            if (s[i] == k) { // 超过范围
                if (i == 0) return ""; // 无法进位
                // 进位
                s[i] = 'a';
                ++s[--i];
            } else if (i > 0 && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
                ++s[i]; // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
            } else {
                ++i; // 检查 s[i] 是否和后面的字符形成回文串
            }
        }
        return new String(s);
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        k += 'a';
        int n = s.length(), i = n - 1;
        ++s[i]; // 从最后一个字母开始
        while (i < n) {
            if (s[i] == k) { // 超过范围
                if (i == 0) return ""; // 无法进位
                // 进位
                s[i] = 'a';
                ++s[--i];
            } else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
                ++s[i]; // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
            } else {
                ++i; // 检查 s[i] 是否和后面的字符形成回文串
            }
        }
        return s;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func smallestBeautifulString(S string, k int) string {
	limit := 'a' + byte(k)
	s := []byte(S)
	n := len(s)
	i := n - 1
	s[i]++ // 从最后一个字母开始
	for i < n {
		if s[i] == limit { // 超过范围
			if i == 0 { // 无法进位
				return ""
			}
			// 进位
			s[i] = 'a'
			i--
			s[i]++
		} else if i > 0 && s[i] == s[i-1] || i > 1 && s[i] == s[i-2] {
			s[i]++ // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
		} else {
			i++ // 检查 s[i] 是否和后面的字符形成回文串
		}
	}
	return string(s)
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。注意不是 \mathcal{O}(nk)，因为只考虑相邻或者相隔一个字母的情况，s[i] 不会增加很多次。
  • 空间复杂度：\mathcal{O}(n) 或 \mathcal{O}(1)。如果可以直接修改字符串（例如 C++）就只需要 \mathcal{O}(1) 的额外空间。

思考题

如果把「不包含任何长度为 2」这里的 2 改成 3，改成 4，改成一个输入的数字 m，要怎么做呢？

 Comments
On this page
2663-字典序最小的美丽字符串
  1. 本题视频讲解
  2. 提示 1
  3. 提示 2
  4. 复杂度分析
  5. 思考题