Description
A happy string is a string that:
- consists only of letters of the set
['a', 'b', 'c'].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).
For example, strings "abc", "ac", "b" and "abcbabcbcb" are all happy strings and strings "aa", "baa" and "ababbc" are not happy strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
Example 1:
Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".
Example 2:
Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.
Example 3:
Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"
Constraints:
1 <= n <= 101 <= k <= 100
Solutions
Solution 1: DFS
We use a string s to record the current string, initially an empty string. Then, we design a function dfs to generate all happy strings of length n.
The implementation of the function dfs is as follows:
- If the length of the current string is equal to n, add the current string to the answer array ans and return;
- If the length of the answer array is greater than or equal to k, return directly;
- Otherwise, we iterate over the character set {a, b, c}. For each character c, if the current string is empty or the last character of the current string is not equal to c, add the character c to the current string, then recursively call dfs. After the recursion ends, remove the last character of the current string.
Finally, we check if the length of the answer array is less than k. If it is, return an empty string; otherwise, return the k-th element of the answer array.
The time complexity is O(n × 2n), and the space complexity is O(n). Here, n is the length of the string.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def getHappyString(self, n: int, k: int) -> str:
def dfs():
if len(s) == n:
ans.append("".join(s))
return
if len(ans) >= k:
return
for c in "abc":
if not s or s[-1] != c:
s.append(c)
dfs()
s.pop()
ans = []
s = []
dfs()
return "" if len(ans) < k else ans[k - 1](code-box)
class Solution {
private List<String> ans = new ArrayList<>();
private StringBuilder s = new StringBuilder();
private int n, k;
public String getHappyString(int n, int k) {
this.n = n;
this.k = k;
dfs();
return ans.size() < k ? "" : ans.get(k - 1);
}
private void dfs() {
if (s.length() == n) {
ans.add(s.toString());
return;
}
if (ans.size() >= k) {
return;
}
for (char c : "abc".toCharArray()) {
if (s.isEmpty() || s.charAt(s.length() - 1) != c) {
s.append(c);
dfs();
s.deleteCharAt(s.length() - 1);
}
}
}
}(code-box)
class Solution {
public:
string getHappyString(int n, int k) {
vector<string> ans;
string s = "";
auto dfs = [&](this auto&& dfs) -> void {
if (s.size() == n) {
ans.emplace_back(s);
return;
}
if (ans.size() >= k) {
return;
}
for (char c = 'a'; c <= 'c'; ++c) {
if (s.empty() || s.back() != c) {
s.push_back(c);
dfs();
s.pop_back();
}
}
};
dfs();
return ans.size() < k ? "" : ans[k - 1];
}
};(code-box)
func getHappyString(n int, k int) string {
ans := []string{}
var s []byte
var dfs func()
dfs = func() {
if len(s) == n {
ans = append(ans, string(s))
return
}
if len(ans) >= k {
return
}
for c := byte('a'); c <= 'c'; c++ {
if len(s) == 0 || s[len(s)-1] != c {
s = append(s, c)
dfs()
s = s[:len(s)-1]
}
}
}
dfs()
if len(ans) < k {
return ""
}
return ans[k-1]
}(code-box)
function getHappyString(n: number, k: number): string {
const ans: string[] = [];
const s: string[] = [];
const dfs = () => {
if (s.length === n) {
ans.push(s.join(''));
return;
}
if (ans.length >= k) {
return;
}
for (const c of 'abc') {
if (!s.length || s.at(-1)! !== c) {
s.push(c);
dfs();
s.pop();
}
}
};
dfs();
return ans[k - 1] ?? '';
}(code-box)
impl Solution {
pub fn get_happy_string(n: i32, k: i32) -> String {
let mut ans = Vec::new();
let mut s = String::new();
let mut k = k;
fn dfs(n: i32, s: &mut String, ans: &mut Vec<String>, k: &mut i32) {
if s.len() == n as usize {
ans.push(s.clone());
return;
}
if ans.len() >= *k as usize {
return;
}
for c in "abc".chars() {
if s.is_empty() || s.chars().last() != Some(c) {
s.push(c);
dfs(n, s, ans, k);
s.pop();
}
}
}
dfs(n, &mut s, &mut ans, &mut k);
if ans.len() < k as usize {
"".to_string()
} else {
ans[(k - 1) as usize].clone()
}
}
}(code-box)
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getHappyString = function (n, k) {
const ans = [];
const s = [];
const dfs = () => {
if (s.length === n) {
ans.push(s.join(''));
return;
}
if (ans.length >= k) {
return;
}
for (const c of 'abc') {
if (!s.length || s.at(-1) !== c) {
s.push(c);
dfs();
s.pop();
}
}
};
dfs();
return ans[k - 1] ?? '';
};(code-box)
public class Solution {
public string GetHappyString(int n, int k) {
List<string> ans = new List<string>();
StringBuilder s = new StringBuilder();
void Dfs() {
if (s.Length == n) {
ans.Add(s.ToString());
return;
}
if (ans.Count >= k) {
return;
}
foreach (char c in "abc") {
if (s.Length == 0 || s[s.Length - 1] != c) {
s.Append(c);
Dfs();
s.Length--;
}
}
}
Dfs();
return ans.Count < k ? "" : ans[k - 1];
}
}(code-box)
Solution 2: Mathematics
We can directly calculate what the k-th happy string is, without generating all happy strings.
Starting from the first happy string of length n, we can determine what each character position should be.
For a happy string of length n, the first character has 3 choices, the second character has 2 choices (cannot be the same as the first), the third character also has 2 choices (cannot be the same as the second), and so on, until the n-th character also has 2 choices (cannot be the same as the (n-1)-th). Therefore, the total number of happy strings of length n is 3 × 2n-1.
If k is greater than the total number of happy strings of length n, we return an empty string directly.
Otherwise, we start from the first character and determine each character's position one by one. For the i-th character, we enumerate the character set {a, b, c}. If the last character of the current string is not equal to c, we calculate the number of remaining happy strings. If k is less than or equal to that count, we append character c to the current string and move on to the next position; otherwise, we subtract that count from k and continue enumerating the next character.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def getHappyString(self, n: int, k: int) -> str:
if k > 3 * (1 << (n - 1)):
return ""
cs = "abc"
ans = []
for i in range(n):
remain = 1 << (n - i - 1)
for c in cs:
if ans and ans[-1] == c:
continue
if k <= remain:
ans.append(c)
break
k -= remain
return "".join(ans)(code-box)
class Solution {
public String getHappyString(int n, int k) {
if (k > 3 * (1 << (n - 1))) {
return "";
}
String cs = "abc";
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; i++) {
int remain = 1 << (n - i - 1);
for (char c : cs.toCharArray()) {
if (ans.length() > 0 && ans.charAt(ans.length() - 1) == c) {
continue;
}
if (k <= remain) {
ans.append(c);
break;
}
k -= remain;
}
}
return ans.toString();
}
}(code-box)
class Solution {
public:
string getHappyString(int n, int k) {
if (k > 3 * (1 << (n - 1))) {
return "";
}
string cs = "abc";
string ans;
for (int i = 0; i < n; ++i) {
int remain = 1 << (n - i - 1);
for (char c : cs) {
if (!ans.empty() && ans.back() == c) {
continue;
}
if (k <= remain) {
ans.push_back(c);
break;
}
k -= remain;
}
}
return ans;
}
};(code-box)
func getHappyString(n int, k int) string {
if k > 3*(1<<(n-1)) {
return ""
}
cs := "abc"
ans := make([]byte, 0, n)
for i := 0; i < n; i++ {
remain := 1 << (n - i - 1)
for j := 0; j < len(cs); j++ {
c := cs[j]
if len(ans) > 0 && ans[len(ans)-1] == c {
continue
}
if k <= remain {
ans = append(ans, c)
break
}
k -= remain
}
}
return string(ans)
}(code-box)
function getHappyString(n: number, k: number): string {
if (k > 3 * (1 << (n - 1))) {
return '';
}
const cs = 'abc';
const ans: string[] = [];
for (let i = 0; i < n; i++) {
const remain = 1 << (n - i - 1);
for (const c of cs) {
if (ans.at(-1) === c) {
continue;
}
if (k <= remain) {
ans.push(c);
break;
}
k -= remain;
}
}
return ans.join('');
}(code-box)
impl Solution {
pub fn get_happy_string(n: i32, mut k: i32) -> String {
if k > 3 * (1 << (n - 1)) {
return String::new();
}
let cs = ['a', 'b', 'c'];
let mut ans: Vec<char> = Vec::with_capacity(n as usize);
for i in 0..n {
let remain = 1 << (n - i - 1);
for &c in &cs {
if !ans.is_empty() && *ans.last().unwrap() == c {
continue;
}
if k <= remain {
ans.push(c);
break;
}
k -= remain;
}
}
ans.into_iter().collect()
}
}(code-box)
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getHappyString = function (n, k) {
if (k > 3 * (1 << (n - 1))) {
return '';
}
const cs = 'abc';
const ans = [];
for (let i = 0; i < n; i++) {
const remain = 1 << (n - i - 1);
for (let j = 0; j < cs.length; j++) {
const c = cs[j];
if (ans.at(-1) === c) {
continue;
}
if (k <= remain) {
ans.push(c);
break;
}
k -= remain;
}
}
return ans.join('');
};(code-box)
public class Solution {
public string GetHappyString(int n, int k) {
if (k > 3 * (1 << (n - 1))) {
return "";
}
string cs = "abc";
var ans = new System.Text.StringBuilder();
for (int i = 0; i < n; i++) {
int remain = 1 << (n - i - 1);
foreach (char c in cs) {
if (ans.Length > 0 && ans[ans.Length - 1] == c) {
continue;
}
if (k <= remain) {
ans.Append(c);
break;
}
k -= remain;
}
}
return ans.ToString();
}
}(code-box)
