Hard

题目描述

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

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

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

返回长度为 n 且字典序大于 s 的字典序最小的美丽字符串。如果不存在这样的字符串，返回一个空字符串。

如果在第一个不同的位置上，字符串 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^5
  • 4 <= k <= 26
  • s 是一个美丽字符串。

解题思路

这道题的核心思想是贪心算法，从右到左寻找可以增加的字符位置。

关键观察：

  1. 如果字符串不包含长度为2和3的回文子串，那么它就不包含任何回文子串
  2. 为了避免回文，当前字符不能与前一个字符相同（长度2回文），也不能与前两个字符相同（长度3回文）

算法步骤：

  1. 从右到左遍历：寻找第一个可以增加的位置i，使得增加后不会创建回文
  2. 增加字符：将位置i的字符增加到下一个有效字符（不与前面字符形成回文）
  3. 重置后续字符：将位置i之后的所有字符重置为’a’，然后逐个调整避免回文
  4. 构造剩余部分：从位置i+1开始，为每个位置选择最小的有效字符

时间优化：通过预处理和贪心选择，每个位置最多尝试3个字符（因为k>=4，总能找到不冲突的字符）。

代码实现

class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int n = s.length();
        vector<char> result(s.begin(), s.end());
        
        // 从右到左寻找可以增加的位置
        for (int i = n - 1; i >= 0; i--) {
            // 尝试增加当前字符
            for (char c = result[i] + 1; c < 'a' + k; c++) {
                // 检查是否与前面的字符形成回文
                if ((i == 0 || c != result[i-1]) && 
                    (i <= 1 || c != result[i-2])) {
                    result[i] = c;
                    
                    // 重新构造后面的字符
                    for (int j = i + 1; j < n; j++) {
                        for (char next = 'a'; next < 'a' + k; next++) {
                            if ((j == 0 || next != result[j-1]) && 
                                (j <= 1 || next != result[j-2])) {
                                result[j] = next;
                                break;
                            }
                        }
                    }
                    
                    return string(result.begin(), result.end());
                }
            }
        }
        
        return "";
    }
};

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        result = list(s)
        
        # 从右到左寻找可以增加的位置
        for i in range(n - 1, -1, -1):
            # 尝试增加当前字符
            for c in range(ord(result[i]) + 1, ord('a') + k):
                char = chr(c)
                # 检查是否与前面的字符形成回文
                if ((i == 0 or char != result[i-1]) and 
                    (i <= 1 or char != result[i-2])):
                    result[i] = char
                    
                    # 重新构造后面的字符
                    for j in range(i + 1, n):
                        for next_c in range(ord('a'), ord('a') + k):
                            next_char = chr(next_c)
                            if ((j == 0 or next_char != result[j-1]) and 
                                (j <= 1 or next_char != result[j-2])):
                                result[j] = next_char
                                break
                    
                    return ''.join(result)
        
        return ""

public class Solution {
    public string SmallestBeautifulString(string s, int k) {
        int n = s.Length;
        char[] result = s.ToCharArray();
        
        // 从右到左寻找可以增加的位置
        for (int i = n - 1; i >= 0; i--) {
            // 尝试增加当前字符
            for (char c = (char)(result[i] + 1); c < 'a' + k; c++) {
                // 检查是否与前面的字符形成回文
                if ((i == 0 || c != result[i-1]) && 
                    (i <= 1 || c != result[i-2])) {
                    result[i] = c;
                    
                    // 重新构造后面的字符
                    for (int j = i + 1; j < n; j++) {
                        for (char next = 'a'; next < 'a' + k; next++) {
                            if ((j == 0 || next != result[j-1]) && 
                                (j <= 1 || next != result[j-2])) {
                                result[j] = next;
                                break;
                            }
                        }
                    }
                    
                    return new string(result);
                }
            }
        }
        
        return "";
    }
}

var smallestBeautifulString = function(s, k) {
    const n = s.length;
    const arr = s.split('');
    
    // Helper function to check if character at position i is valid
    const isValid = (arr, i, char) => {
        if (i > 0 && arr[i-1] === char) return false;
        if (i > 1 && arr[i-2] === char) return false;
        return true;
    };
    
    // Try to increment from right to left
    for (let i = n - 1; i >= 0; i--) {
        // Try to increment current character
        for (let c = arr[i].charCodeAt(0) + 1; c < 97 + k; c++) {
            const char = String.fromCharCode(c);
            if (isValid(arr, i, char)) {
                arr[i] = char;
                
                // Fill the rest with smallest valid characters
                for (let j = i + 1; j < n; j++) {
                    for (let nextC = 97; nextC < 97 + k; nextC++) {
                        const nextChar = String.fromCharCode(nextC);
                        if (isValid(arr, j, nextChar)) {
                            arr[j] = nextChar;
                            break;
                        }
                    }
                }
                
                return arr.join('');
            }
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(n)

时间复杂度分析：

  • 外层循环最多遍历n个位置
  • 对于每个位置，最多尝试k个字符，但由于k≥4且只需避免与前2个字符冲突，实际最多尝试3次
  • 重构后续字符时，每个位置最多尝试3个字符
  • 总体时间复杂度为O(n)

空间复杂度分析：

  • 使用了长度为n的数组存储结果字符串
  • 空间复杂度为O(n)

相关题目