Leetcode 2663. Lexicographically Smallest Beautiful String

[Woodyiiiiiii]

2663. Lexicographically Smallest Beautiful String

• 2663. Lexicographically Smallest Beautiful String
• 赛事活动｜[第343场周赛]式酱的解题报告

这道题是纯纯的思维题。

最重要的当然是挖掘性质。关键是beautiful string第二个要求，它的长度等于大于2的子串没有 palindrome。翻译过来，根据传递性，也就是其所有子串不是palindrome，只需要判断左侧两个字符s[i] != s[i-1] && s[i] != s[i-2]。

那么剩下的思路就简单了，倒序遍历字符串，尝试能否对当前字符替换较大值，同时与前两个字符比较是否构成palindrome，一旦能替换，则对之后的字符"abc"循环构建。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    public String smallestBeautifulString(String s, int k) {
        String res = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            int idx = c - 'a';
            for (int j = idx + 1; j < k; j++) {
                char cc = (char)('a' + j);
                if (i - 1 >= 0 && s.charAt(i - 1) == cc) {
                    continue;
                }
                if (i - 2 >= 0 && s.charAt(i - 2) == cc) {
                    continue;
                }
                res = s.substring(0, i) + cc;
                StringBuilder sb = new StringBuilder(res);
                for (int jj = i + 1; jj < s.length(); jj++) {
                    for (int kk = 0; kk < 3; kk++) {
                        char ccc = (char)('a' + kk);
                        if (jj - 1 >= 0 && sb.charAt(jj - 1) == ccc) {
                            continue;
                        }
                        if (jj - 2 >= 0 && sb.charAt(jj - 2) == ccc) {
                            continue;
                        }
                        sb.append(ccc);
                        break;
                    }
                }
                return sb.toString();
            }
        }
        return res;
    }
}