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
This function generates the k-th happy string of length n using a stack-based depth-first search. A "happy string" is one where no two adjacent characters are the same, using only the letters 'a', 'b', and 'c'. The algorithm starts with an empty string and iteratively builds longer strings by pushing candidates onto a stack—but only pushes a character if it's different from the last character in the current string (checked with conditions like s[s.length - 1] !== 'a'). When a string reaches the target length n, it counts down the counter k; once k reaches 0, that string is the answer and gets returned. If the stack empties without finding the k-th string, it returns an empty string (meaning there aren't k valid happy strings of that length).
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getHappyString = function(n, k) {
const stack = [''];
while (stack.length > 0) {
const s = stack.pop();
if (s.length === n) {
k--;
if (k === 0) {
return s;
}
continue;
}
if (!s || s[s.length - 1] !== 'c') stack.push(s + 'c');
if (!s || s[s.length - 1] !== 'b') stack.push(s + 'b');
if (!s || s[s.length - 1] !== 'a') stack.push(s + 'a');
}
return '';
};