题目描述

一个 开心字符串 定义为：

• 仅包含小写字母 ['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 个，那么请你返回 空字符串。

样例

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

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

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

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

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

限制

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

算法1

(递归枚举) $O(nk)$

1. 递归按照字典序直接构造合法字符串，到达长度 n 时，k 减 1，直到 k 为 0 时的当前字符串为答案。

时间复杂度

• 构造一个答案平均需要 $O(n)$ 的时间，故时间复杂度为 $O(nk)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储系统栈和存储答案。

C++ 代码

class Solution {
public:
    bool solve(int x, string &cur, int &k) {
        if (x == 0) {
            k--;
            if (k == 0) return true;
            return false;
        }

        for (char c = 'a' ; c <= 'c'; c++)
            if (cur.size() == 0 || cur.back() != c) {
                cur += c;
                if (solve(x - 1, cur, k))
                    return true;
                cur.pop_back();
            }

        return false;
    }

    string getHappyString(int n, int k) {
        string cur;
        if (solve(n, cur, k))
            return cur;
        return "";
    }
};

算法2

(动态规划) $O(n)$

1. 设 $f(i, j)$ 表示填充了区间 [0, i]，且以字符 $j$ 结尾的合法字符串的数量。
2. 初始值 $f(0, 0) = f(0, 1) = f(0, 2) = 1$，其余为 0。
3. 转移时，如果 $j \neq k$，则 $f(i, k) = f(i, k) + f(i - 1, j)$。
4. 我们根据 $f$ 数组来构造答案。
5. 我们不妨给 $f$ 数组换一个等价的状态定义：假设我们是从后向前填的字符串，状态定义可以等价的换成填充了区间 [i, n - 1]，且以 $j$ 开头的合法字符串的数量，即每次向前添加字符。
6. 如果 $k > f(n - 1, 0) + f(n - 1, 1) + f(n - 1, 2)$，则显然解不存在。
7. 否则我们从开头构造答案，定义变量 last 表示上个字符。令当前 $i = n - 1$，我们找到最小的 $j_0$，满足 $k > \sum_{j=0, j \neq last}^{j_0 - 1}{f(i, j)}$。当前字符就是 $j_0$，然后令 k 减去之前的求和式。
8. 如此迭代到 $i=0$，我们就完成了答案构造。

时间复杂度

• 动态规划的时间复杂度为 $O(n)$，构造答案的时间复杂度也为 $O(n)$。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态和答案。

C++ 代码

class Solution {
public:
    string getHappyString(int n, int k) {
        vector<vector<int>> f(n, vector<int>(3, 0));
        f[0][0] = f[0][1] = f[0][2] = 1;
        for (int i = 1; i < n; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    if (j != k)
                        f[i][k] += f[i - 1][j];

        if (k > f[n - 1][0] + f[n - 1][1] + f[n - 1][2])
            return "";

        string ans;
        int last = -1;
        for (int i = n - 1; i >= 0; i--)
            for (int j = 0; j <= 2; j++) {
                if (j == last) continue;
                if (k > f[i][j])
                    k -= f[i][j];
                else {
                    last = j;
                    ans += j + 'a';
                    break;
                }
            }

        return ans;
    }
};