1415. 长度为 n 的开心字符串中字典序第 k 小的字符串
一个 「开心字符串」定义为：
- 仅包含小写字母
['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 <= 101 <= k <= 100
思路
首先，长度为 n 的开心字符串个数为(1<<(n-1))*3，若小于k，则返回空字符串 。
设置一个字符作为已经添加的前一个字符，保证得到开心字符串。
令count_per_choice=1<<(n-i-1)为每添加一个字符所代表的可能性，每次从a到c遍历，若count_per_choice>=k,则取当前字符，跳出循环，否则k-count_per_choice,继续遍历。
点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
string getHappyString(int n, int k) {
int total = 3 * (1 << (n - 1));
if (k > total) return "";
string result;
char prev = '\0';
for (int i = 0; i < n; ++i) {
int count_per_choice = 1 << (n - i - 1); // 2^(n-i-1)
for (char c = 'a'; c <= 'c'; ++c) {
if (c == prev) continue;
if (k <= count_per_choice) {
result += c;
prev = c;
break;
}
k -= count_per_choice;
}
}
return result;
}
};
