the-k-th-lexicographical-string-of-all-happy-strings-of-length-n 1.0.0
The k-th Lexicographical String of All Happy Strings of Length n
Loading...
Searching...
No Matches
Public Member Functions
Solution Class Reference

Public Member Functions

string getHappyString (int n, int k)
 

Detailed Description

Definition at line 5 of file main.cpp.

Member Function Documentation

◆ getHappyString()

string Solution::getHappyString ( int  n,
int  k 
)
inline

Definition at line 8 of file main.cpp.

9 {
10 // if k is larger than possible combinations return ""
11 int combinations = 3 * (int)pow(2, n - 1);
12 if (k > combinations)
13 return "";
14
15 // for (a, b, c) as characters the is exactly combination/3 sequences starting with each char
16 int starting_with_the_same_letter = combinations / 3;
17
18 // build result from the first char
19 string result("");
20 if (k <= starting_with_the_same_letter)
21 result += 'a';
22 else if (k > starting_with_the_same_letter && k <= 2 * starting_with_the_same_letter)
23 result += 'b';
24 else
25 result += 'c';
26
27 // k is adjusted after first char is built
28 k = k % starting_with_the_same_letter;
29 if (k == 0)
30 k = starting_with_the_same_letter;
31
32 // iteratively construct the rest of the answer
33 int half = starting_with_the_same_letter / 2;
34 for (int i = 1; i < n; ++i)
35 {
36 char prev_char = result.back();
37 char first_choice, second_choice;
38
39 switch (prev_char)
40 {
41 case 'a':
42 first_choice = 'b';
43 second_choice = 'c';
44 break;
45 case 'b':
46 first_choice = 'a';
47 second_choice = 'c';
48 break;
49 default:
50 first_choice = 'a';
51 second_choice = 'b';
52 break;
53 }
54
55 if (k <= half)
56 result += first_choice;
57 else
58 {
59 result += second_choice;
60 k -= half;
61 }
62 half /= 2;
63 }
64 return result;
65 }

Referenced by main().

The documentation for this class was generated from the following file: