What defines a beautiful string in this problem?

A beautiful string has no palindromic substrings of length 2 or 3 and uses only the first k lowercase letters.

Why is a greedy approach suitable here?

Greedy choice ensures each character is incremented minimally to maintain lexicographical order while validating the beauty invariant efficiently.

What if no lexicographically larger beautiful string exists?

Return an empty string as no solution can satisfy both the lexicographical and beauty constraints.

How do you verify the string remains beautiful?

Check the last two characters at each step to ensure no palindrome of length 2 or 3 is formed before fixing subsequent positions.

Can GhostInterview help identify failure points in this greedy approach?

Yes, it highlights where increments violate palindromic invariants and shows how to adjust subsequent characters to maintain beauty.

#2663

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

字典序最小的美丽字符串

如果一个字符串满足以下条件，则称其为美丽字符串：它由英语小写字母表的前 k 个字母组成。它不包含任何长度为 2 或更长的回文子字符串。给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中…

字符串贪心

题目描述

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

它由英语小写字母表的前 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 <= 10⁵
4 <= k <= 26
s 是一个美丽字符串

lightbulb

解题思路

方法一：贪心

我们可以发现，一个长度为 $2$ 的回文字符串，其相邻两个字符一定相同；而一个长度为 $3$ 的回文字符串，其首尾两个字符一定相同。因此，一个美丽字符串不包含任何长度为 $2$ 或更长的回文子字符串，意味着该字符串的每个字符与其相邻的前两个字符都不相同。

我们可以贪心地从字符串的最后一个下标开始往前查找，找到一个下标 $i$ ，使得下标 $i$ 处的字符可以被替换为一个比其稍大的字符，同时保证其与其相邻的前两个字符都不相同的字符 $c$ 。

若找到了这样的下标 $i$ ，那么我们将 $s[i]$ 替换为 $c$ ，并将 $s[i+1]$ 到 $s[n-1]$ 的字符依次替换为字典序尽可能小的、不与前面相邻两个字符相同的、且在字母表前 $k$ 个字符中的字符，替换完成后，我们就得到了一个字典序最小的且大于 $s$ 的美丽字符串。
若找不到这样的下标 $i$ ，那么我们就无法构造出字典序大于 $s$ 的美丽字符串，因此返回空字符串。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        cs = list(s)
        for i in range(n - 1, -1, -1):
            p = ord(cs[i]) - ord('a') + 1
            for j in range(p, k):
                c = chr(ord('a') + j)
                if (i > 0 and cs[i - 1] == c) or (i > 1 and cs[i - 2] == c):
                    continue
                cs[i] = c
                for l in range(i + 1, n):
                    for m in range(k):
                        c = chr(ord('a') + m)
                        if (l > 0 and cs[l - 1] == c) or (l > 1 and cs[l - 2] == c):
                            continue
                        cs[l] = c
                        break
                return ''.join(cs)
        return ''

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
They may ask how to efficiently check for palindromic substrings while modifying characters.
question_mark
Expect questions about greedy approaches for lexicographical order with constraints.
question_mark
They might probe the invariant maintenance and early termination strategy.

warning

常见陷阱

外企场景

error
Incrementing a character without checking the palindrome constraint leads to invalid strings.
error
Filling remaining characters without greedy choice can produce non-minimal lexicographical results.
error
Failing to handle the case where no valid larger string exists returns incorrect output.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding the lexicographically largest beautiful string smaller than a given string.
arrow_right_alt
Generalizing to avoid palindromic substrings of length up to m instead of 2 and 3.
arrow_right_alt
Allowing a custom alphabet instead of first k lowercase letters.

help

常见问题

外企场景

继续练习

#2645 构造有效字符串的最少插入数 #2697 字典序最小回文串 #2712 使所有字符相等的最小成本