M1415.长度为 n 的开心字符串中字典序第 k 小的字符串

math, backtracking, https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/

一个 「开心字符串」定义为：

• 仅包含小写字母 ['a', 'b', 'c'].
• 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。

比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。

给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。

示例 1：

输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2：

输入：n = 1, k = 4
输出：""
解释：长度为 1 的开心字符串只有 3 个。

示例 3：

输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4：

输入：n = 2, k = 7
输出：""

示例 5：

输入：n = 10, k = 100
输出："abacbabacb"

提示：

• 1 <= n <= 10
• 1 <= k <= 100

这个问题可以通过数学推导（进制/计数原理）或者回溯算法来解决。由于 $n$ 的范围较小（最大为 10），两种方法都能高效运行。

下面使用数学推导的方法，这种方法的效率最高，时间复杂度为 $O(n)$。

解题思路

1. 总数计算：

   • 第一个字符有 3 种选择（a, b, c）。
   • 从第二个字符开始，为了满足“开心字符串”的条件（相邻字符不同），每个位置都有 2 种选择（即除了前一个字符以外的另外两个字母）。
   • 因此，长度为 $n$ 的开心字符串总共有 $3\times 2^{n-1}$ 个。

2. 逐位确定字符：

   • 第一位：总共有 3 个组，每组包含 $2^{n-1}$ 个字符串。我们可以根据 $k$ 落在哪个区间来确定第一位是 a、b 还是 c。
   • 后续位：一旦确定了前一个字符，当前位只有两个可选字符（按字典序排序）。剩下的 $n-1$ 位中，每一位对应的可选分支会产生 $2^{n-1-i}$ 个字符串。我们根据更新后的 $k$ 值来选择这两个字符中的哪一个。

3. 边界处理：

   • 如果 $k$ 大于总数 $3\times 2^{n-1}$，直接返回空字符串。

代码实现

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        # 1. 计算总共有多少个开心字符串
        # 第一位有3种选择，后面每一位有2种选择
        total = 3 * (2 ** (n - 1))
        
        # 如果 k 超过了总数，直接返回空字符串
        if k > total:
            return ""
        
        # 将 k 转换为从 0 开始的索引，方便进行除法和取余运算
        k -= 1
        
        res = []
        
        # 2. 确定第一个字符
        # 每个起始字符 ('a', 'b', 'c') 后面对应 2^(n-1) 个字符串
        group_size = 1 << (n - 1)
        first_char_index = k // group_size
        res.append(['a', 'b', 'c'][first_char_index])
        
        # 更新 k 值为在当前组内的偏移量
        k %= group_size
        
        # 3. 确定剩下的 n-1 个字符
        for i in range(1, n):
            # 每一位在确定了前一个字符后，剩余的选择支减少一半
            group_size //= 2
            
            # 获取当前位可选的两个字符（除去前一个字符，按字典序排列）
            last_char = res[-1]
            choices = [c for c in ['a', 'b', 'c'] if c != last_char]
            
            # 根据当前的 k 决定选哪一个
            char_index = k // group_size
            res.append(choices[char_index])
            
            # 更新 k
            k %= group_size
            
        return "".join(res)

复杂度分析

• 时间复杂度：$O(n)$。我们只需要遍历长度 $n$ 一次即可确定每一位的字符。
• 空间复杂度：$O(n)$。用于存储结果字符串的字符数组。

示例解析：$n=3,k=9$

1. $n=3$ 时，总数 = $3\times 2^{3-1}=12$。 $k=9\le 12$，可行。
2. 令 $k=8$ (0-indexed)。
3. 第一位：group_size = 4。 8 // 4 = 2。 字符数组 ['a', 'b', 'c'] 下标 2 为 'c'。 k = 8 % 4 = 0。
4. 第二位：group_size = 2。 前一个字符是 'c'，可选 ['a', 'b']。 0 // 2 = 0。下标 0 为 'a'。 k = 0 % 2 = 0。
5. 第三位：group_size = 1。 前一个字符是 'a'，可选 ['b', 'c']。 0 // 1 = 0。下标 0 为 'b'。 k = 0 % 1 = 0。
6. 最终结果为 "cab"。

回溯算法（Backtracking）通过模拟“生成所有开心字符串”的过程来解决此问题。由于题目要求的是字典序第 k 个，我们只需要按照 'a' -> 'b' -> 'c' 的顺序进行深度优先搜索（DFS），并记录当前生成的字符串数量，当数量达到 $k$ 时停止搜索即可。

回溯法解题思路

1. 确定搜索顺序：在每一位尝试放字符时，都按 'a', 'b', 'c' 的顺序尝试，这样能保证最先生成的字符串是字典序最小的。
2. 约束条件：当前尝试放入的字符不能与上一个字符相同。
3. 终止条件：
   • 当生成的字符串长度达到 $n$ 时，计数器 k 减 1。
   • 当 k 减到 0 时，说明找到了第 $k$ 个字符串，保存结果并立即层层返回（剪枝）。
4. 空间与时间：
   • $n$ 最大为 10，总的开心字符串最多有 $3\times 2^9=1536$ 个。
   • 回溯法的时间复杂度在该量级下非常快。

代码实现

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        self.count = 0
        self.res = ""

        def backtrack(path):
            # 如果已经找到了第 k 个，直接返回
            if self.res:
                return

            # 达到目标长度
            if len(path) == n:
                self.count += 1
                if self.count == k:
                    self.res = "".join(path)
                return

            # 字典序尝试 'a', 'b', 'c'
            for char in ['a', 'b', 'c']:
                # 检查是否满足“开心字符串”条件：不与前一个字符相同
                if not path or path[-1] != char:
                    path.append(char)
                    backtrack(path)
                    path.pop()  # 回溯，撤销选择

        backtrack([])
        return self.res

复杂度分析

• 时间复杂度：$O(k\cdot n)$。在最坏的情况下，我们需要找到第 $k$ 个字符串。每个字符的生成需要 $O(1)$ 的选择，总共生成 $k$ 个长度为 $n$ 的字符串。由于题目 $k\le 100,n\le 10$，计算量非常小。
• 空间复杂度：$O(n)$。主要是递归栈的深度，最大深度为 $n$。

两种方法的对比

特性	数学推导 (贪心/进制)	回溯法 (DFS)
性能	$O(n)$，极快	$O(k\cdot n)$，受 $k$ 影响
代码难度	逻辑需仔细考虑 $2^{n-i}$ 关系	逻辑直观，模板化
适用场景	$n$ 很大时（如 $n=100$）	$n$ 和 $k$ 较小时

总结：对于本题的参数规模，回溯法更容易编写且不易出错；但如果 $n$ 增加到 100 以上，回溯法会超时，必须使用第一种数学推导法。