网站更改文章标题域名收录查询

题目

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

• 它由英语小写字母表的前 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" 的字符串。

思路

前提：如果字符串不包含任何长度为 2 和 3 的回文子字符串，则该字符串根本不包含任何回文子字符串。

题目简单来说就是在有限的字母范内给你一个没有回文子字符串的字符串，返回比这个字符串大的最小字符串，注意要在范围内，否则返回空字符串。

解题方法

由于原字符串已经是美丽字符串，所以我们只需要将最后一位加1，进行判断，首先看有没有超出字母范围，如果超出，赋最小的值a，进位，判断是否能进位，不能返归空字符串。再判断是否构成回文字符串，i>0&&str[i]==str[i-1]||i>1&&str[i]==str[i-2]是的话，数值加一，否则在i<n里判断后面是否构成回文字符串。构成就加1，不构成i++,每一次都会判断有没有超出字母范围，如果超出，赋最小的值a，进位。

代码

class Solution {public String smallestBeautifulString(String s, int k) {int n=s.length();k=k+'a';char[] str=s.toCharArray();int i=n-1;str[i]++;while(i<n){if(str[i]==k){if(i==0){return "";}str[i]='a';str[--i]++;}else if(i>0&&str[i]==str[i-1]||i>1&&str[i]==str[i-2]){str[i]++;}else{i++;}}return new String(str);}
}