1415.长度为 n 的开心字符串中字典序第 k 小的字符串：DFS构造 / 数学O(1)

【LetMeFly】1415.长度为 n 的开心字符串中字典序第 k 小的字符串：DFS构造 / 数学O(n)

力扣题目链接：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

 

解题方法一：DFS构造

写一个dfs函数接收已经构造的字符串并继续构造字符串：

• 如果之前字符串已经长度为n了，就看看这是不是第k次长度为n。如果是，则说明找到了答案；否则，不继续向后追加字符串，结束这层递归在其他层递归继续寻找答案。
• 否则，尝试把abc中每个和上一个字符(如有)不同的字符拼接到字符串上并递归。

特别的，我们可以控制这个函数的返回值，返回true代表已经找到了最终答案，可以不再进行后续递归。

• 时间复杂度$O(nk)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-14 23:29:38
 */
class Solution {
private:
    int n, k;
    string ans;
    char can[3] = {'a', 'b', 'c'};

    // dfs and return if can stop
    bool dfs(string now) {
        if (now.size() == n) {
            k--;
            if (!k) {
                ans = now;
                return true;
            }
            return false;
        }

        char last = now.empty() ? '0' : now.back();
        for (int i = 0; i < 3; i++) {
            if (can[i] == last) {
                continue;
            }
            if (dfs(now + can[i])) {
                return true;
            }
        }
        return false;   
    }
public:
    string getHappyString(int n, int k) {
        this->n = n, this->k = k;
        dfs("");
        return ans;
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
1 3

c
*/
int main() {
    int a, b;
    while (cin >> a >> b) {
        Solution sol;
        cout << sol.getHappyString(a, b) << endl;
    }
    return 0;
}
#endif

解题方法二：数学直接找

长度为$n$的字符串一共有多少种开心字符串呢？

第一个字符有$3$种选择，后续每个字符有$2$种选择，共计$3\times2^{n-1}$种。

如果$k\gt 3\times2^{n-1}$则答案不存在，返回空串。

第$k$个开心字符串的每一位分别应该对应哪个字符呢？很简单，我们只需要计算下这个字符后面字符串有多少种。

举个例子：

• 假设后面字符串有$2^2$共4种，而当前$k=3\leq 4$，那么当前字符选哪个？当然选能选的字符中第一个就够了；
• 假设后面字符串有$2^2$共4种，而当前$k=5\lt 4$，那么当前字符选哪个？当然选能选的字符中第二个，因为选第一个的话后面最多$4$种情况，到不了$k=5$。

PS: 上面的“能选的字符”指的是属于abc且和前一个字符不同的字符。

选完这个字符后，令$k$对剩余种类数取模，并更新剩余字符的种类数。

为什么取模呢？

• 仍然假设后面字符串有$2^2$共4种，而当前$k=5\lt 4$，假设当前可选字符为ab，那么相当于当前选a时候后面共有$4$个开心字符串，后面选完了当前字符确定选b了，后面还需要$5%4=1$个开心字符串，使得总开心字符串数是当前$k=5$个。

我们也可以将$k-1$以便后面的取模整除运算。

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-14 23:21:37
 */
class Solution {
public:
    string getHappyString(int n, int k) {
        int remain = 1 << (n - 1);
        if (k > 3 * remain) {
            return "";
        }
        
        k--;
        char toChoose[3] = {'a', 'b', 'c'};
        string ans;
        ans.push_back(toChoose[k / remain]);
        for (int i = 1; i < n; i++) {
            k %= remain;
            remain >>= 1;
            int th = k / remain;
            if (toChoose[th] >= ans.back()) {
                th++;
            }
            ans.push_back(toChoose[th]);
        }
        return ans;
    }
};

感觉描述得还不错哈哈。

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源