1415. The k-th Lexicographical String of All Happy Strings of Length n
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 ofifrom1tos.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 $\textit{s}$ to record the current string, initially an empty string. Then, we design a function $\text{dfs}$ to generate all happy strings of length $n$.
The implementation of the function $\text{dfs}$ is as follows:
If the length of the current string is equal to $n$, add the current string to the answer array $\textit{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 $\text{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 \times 2^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string.
Python3
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]
Java
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);
}
}
}
}
C++
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];
}
};
Go
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]
}
TypeScript
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] ?? '';
}
Rust
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()
}
}
}
JavaScript
/**
* @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] ?? '';
};
C#
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];
}
}