The k-th Lexicographical String of All Happy Strings of Length n

A happy string uses only a, b, and c and adjacent characters differ. Do not generate all strings unless n is tiny. After a chosen first character, every later position has exactly two legal choices, so a valid prefix with r positions remaining has 2^r completions. At each position, try legal next letters in alphabetical order. If k is larger than the completion count for a candidate, subtract that count and skip its entire branch; otherwise choose it. Before starting, check whether k exceeds 3*2^(n-1) and return the required empty result. This direct unranking takes O(n) time and O(n) output space; cap counts above k to avoid overflow. Test k=1, the final valid k, n=1, and a k just beyond the total.