首页算法

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

难度困难

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

  • 它由英语小写字母表的前 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 是一个美丽字符串

# 类似于数位 dp 的 dfs

可以从头开始对每一位填入相应的字符

定义 dfs(pre,ppre,i,isOrigin)dfs(pre, ppre, i, isOrigin) 为填入 ii 位的字符串

  • prepre：i−1i - 1 位填入的字符
  • ppreppre：i−2i - 2 位填入的字符
  • ii：当前 ii 位
  • isOriginisOrigin：前面是否是原始字符

若 isOrigin==trueisOrigin == true，说明前面是原始字符 s[i]s[i]

  • 当前位可以填入 s[i]s[i]，也可以填入 s[i]+1s[i] + 1~ [k][k] 的字符

若 isOrigin==falseisOrigin == false，可以填入 ′a′'a'~ kk 的字符

若 i==s.lengthi == s.length，说明满足最小字典序的字符串，返回即可。

class Solution {
    public String smallestBeautifulString(String s, int k) {
        this.s = s;
        this.k = k;
        StringBuilder dfs = dfs(-1, -1, 0, true);
        return dfs == null ? "" : dfs.reverse().toString();
    }
    String s;
    int k;
    public StringBuilder dfs(int pre, int ppre, int i, boolean isOrigin) {
        // 到这步说明是最小的，一直返回答案
        if (i == s.length()) {
            return isOrigin ? null : new StringBuilder();
        }
        int c = s.charAt(i) - 'a';
        // 当前字符可以增大可以不增大 (原始字符)
        if (isOrigin) {
            // 只有不是回文才会进入递归
            if (c <= k && c != ppre && c != pre) {
                StringBuilder dfs = dfs(s.charAt(i) - 'a', pre, i + 1, true);
                if (dfs != null) {
                    return dfs.append(s.charAt(i));
                }
            }
        }
        // 若增大，下一位可填入范围 ['a', k]
        // 若上一位增大，当前位可填入范围 ['a', k]
        //  否则: [s [i] + 1, k]
        int j = isOrigin ? c + 1 : 0;
        for (; j < k; j++) {
            if (pre != j && ppre != j) {
                StringBuilder dfs = dfs(j, pre, i + 1, false);
                if (dfs != null) {
                    return dfs.append((char) (j + 'a'));
                }
            }
        }
        return null;
    }
}
# 贪心 - 1




参考灵神题解：贪心




首先要让结果字典序最小，修改的位置越靠后越好




把 ss 看作是一个 kk 进制数理解。例如：aa 看作 0，...




例如：s=dacds= dacd，k=4k = 4


首先先将末尾的 s[3]=ds[3] = d 加一，进位得到 s=dadas = dada ，此时 ss 是最小的字符串，可以发现 ss 中前 33 位与后 33 位形成了回文串。


首先考虑前面的，将 s[2]=ds[2] = d 加一，进位得到 s=dbaas=dbaa，此时 ss 是最小的字符串。




为什么此时 ss 是最小的字符串？若先考虑后面的呢？


    

  • 因为前面是回文，无论是否考虑后面当前位必然要加一，没有必要先考虑后面
    • 





由于前面满足不是回文，检查当前位后面是否有回文串。将 s[3]=as[3] = a 加一，得到 s=dbabs = dbab，前面两位依然是回文串。


再次将 s[3]=bs[3] = b 加一，得到 s=dbacs = dbac，此时前面都不是回文字符串，检查后面的是否满足：i+1i + 1


class Solution {
    public String smallestBeautifulString(String s1, int k) {
        // 从 n - 1 开始
        char[] s = s1.toCharArray();
        k += 'a';
        int n = s.length;
        int i = n - 1;
        s[i]++;
        while (i < n) {
            // 封顶了
            if (s[i] == k) {
                // 第一个字符都不行
                if (i == 0) {
                    return "";
                }
                s[i] = 'a';
                // 进位，检查 i - 1 是否与前面构成回文
                s[--i]++;
            } else if (i > 0 && s[i - 1] == s[i] || i > 1 && s[i - 2] == s[i]) {
                // 有一个是回文
                s[i]++;
            } else {
                // 说明前面已经是美丽字符串，检查后面的
                i++;
            }
        }
        return new String(s);
    }
}
# 复杂度分析


    

  • 时间复杂度：O(n)O(n)，其中 nn 为 ss 的长度，由于只考虑相邻或者相隔一个字母的情况，s[i]s[i] 不会增加很多次。
    • 

  • 空间复杂度：O(n)O(n)
    • 



# 贪心 - 2


首先要让结果字典序最小，修改的位置越靠后越好。


从 n−1n - 1 开始不断向前遍历 ii，寻找前 ii 个字符能构成美丽字符串（不是回文）的最大下标 i+1i + 1


对于第 ii 位，枚举 s[i]+1∼ks[i] + 1\sim k 范围内的字母 jj


    

  • j !=s[i−1] && j !=s[i−2]j \,!= s[i - 1]\, \&\&\, j\, != s[i - 2]，则满足条件，返回 i+1i + 1
    • 

  • 若 jj 都不满足上述，i−1i - 1，检查前一位是否满足
    • 



若上述最大下标 i+1==−1i + 1 == -1，说明构造不出来，返回 ""。


否则从 i+1∼n−1i + 1\sim n - 1 开始进行贪心构造即可。


class Solution {
    public String smallestBeautifulString(String s1, int k) {
        // 从 n - 1 开始
        char[] s = s1.toCharArray();
        k += 'a';
        int n = s.length;
        int pos = helper(s, n - 1, k);
        if (pos == -1) {
            return "";
        }
        // 从 [pos, n - 1] 贪心构造，后面的字符范围 ['a', k]
        for (int i = pos; i < n; i++) {
            for (char j = 'a'; j < k; j++) {
                if (i > 0 && s[i - 1] == j || i > 1 && s[i - 2] == j) {
                    continue;
                }
                s[i] = j;
                break;
            }
        }
        return new String(s);
    }
    public int helper(char[] s, int pos, int k) {
        while (pos >= 0) {
            // [s [pos] + 1 ~ k] 构造字符
            for (char i = (char) (s[pos] + 1); i < k; i++) {
                if (pos > 0 && s[pos - 1] == i || pos > 1 && s[pos - 2] == i) {
                    continue;
                }
                s[pos] = i;
                return pos + 1;
            }
            pos--;
        }
        return -1;
    }
}
# 复杂度分析


    

  • 时间复杂度：O(C∗n)O(C * n)，其中 nn 为 ss 的长度，C=26C = 26
    • 

  • 空间复杂度：O(n)O(n)
    •