Thought
The Sum Array
Definition
Consider we have an array sum[len][char] to store the total number of happy strings start with char when the total length is len.
char: We use0, 1, 2to representa, b, cherelen: An non-negative integer specify the total length of the string
Array Elements
Let’s find the recursive relations between the elements in this array.
sum[len][0] = sum[len - 1][1] + sum[len - 1][2]This is easy to understand: If the n-length happy string starting with a, then it could be:
"a" + any_happy_str(start="b", length=n - 1)
"a" + any_happy_str(start="c", length=n - 1)The similar rule applies to sum[len][1] and sum[len][2], they just add up the value of array elements representing different starting characters in n - 1 length layer.
If we calculate the element based on this rule, we will find out the final array looks like the one below:
len 0 1 2 3 4 5 6 7 ...
===============================
[a] 0 1 2 4 8 16 32 64 ...
[b] 0 1 2 4 8 16 32 64 ...
[c] 0 1 2 4 8 16 32 64 ...
So the char dimension is unnecessary, and we have:
sum[length] = power_of_two(length - 1) # length >= 1Calculate -th Happy String with Length
Let’s start with the first character, we need to check about the sum array, the logic is like below:
if k <= arr[n][0]:
first = 'a'
else if k <= arr[n][0] + arr[n][1]:
first = 'b'
else if k <= arr[n][0] + arr[n][1] + arr[n][2]:
first = 'c'
else:
raise NoAnswer("Total number of happy strings is less than k")If we use the optimized sum array definitions described below in Array Elements, we have:
if k <= arr[n]:
first = 'a'
else if k <= arr[n] * 2:
first = 'b'
else if k <= arr[n] * 3:
first = 'c'
else:
raise NoAnswer("Total number of happy strings is less than k")Now, let’s consider how to actually determine every character in the happy string based on length and sequence number .
Define that “sequence number” as the index of the happy string in terms of lexical order starting at . For example, if there is an answer, then the answer’s sequence number will be . In another word, sequence number is that “how many happy strings before this happy string in terms of dictionary order”.
determined[]: Store already determined charactersoffset: Store the smallest possible sequence number ofdetermined[]
When we say the smallest possible sequence number of determined[], we are say that we assume that we choose characters for undetermined positions in a way that the final sequence number is the smallest. That actually means we are choosing the sequence of characters for the undetermined positions with the smallest possible lexical directory order.
Based on this, we will have the following algorithm:
# given by question
n = N
k = K
offset = 0
determined: list = []
cur_idx = -1
Char = Literal['a', 'b', 'c']
def valid_offset(v) -> bool:
return v < k
def cur_len() -> int:
return n - cur_idx
def cur_sum() -> int:
# check about "The Sum Array" chapter for more info
return sum[cur_len()]
def possible_choice(idx: num) -> list[Char]:
_all = ['a', 'b', 'c']
if idx == 0:
return _all
return _all.without_element(determined[idx - 1])
def solve() -> str:
while valid_offset(offset) and cur_idx < n:
# update index
# pointing to positions we are going to determine a character for
cur_idx++
ch_list = possible_choice(cur_idx)
find = False
# go through all possible character for this position
for ch in ch_list:
# shift to next possible character if not exceeding
# the required sequence number
if valid_offset(offset + cur_sum()):
continue
# could not shift, then choose this char
find = True
determined.append(ch)
# if we shift until all possible char used up in a certain idx,
# that means we failed to find the answer
# in another word, we could not reach k-th happy string
if not find:
raise NoAnswer()
assert len(determined) == n
return determined.join("")Code Implementation
#include<string>
#include<vector>
using std::string, std::vector;
constexpr unsigned int MAX_N = 10;
class SumTable {
private:
unsigned short m_sum[MAX_N + 1];
public:
constexpr SumTable() :m_sum(MAX_N + 1) {
m_sum[0] = 0;
m_sum[1] = 1;
for (int i = 2; i <= MAX_N; ++i) {
m_sum[i] = m_sum[i - 1] * 2;
}
}
constexpr unsigned short operator[](const size_t& idx) const {
return m_sum[idx];
}
};
constexpr auto sum = SumTable();
class Solution {
private:
vector<char> determined;
unsigned short offset = 0;
unsigned short n;
unsigned short k;
bool valid_offset(const int& v) const {
return v < k;
}
int cur_idx() const {
return determined.size();
}
size_t cur_len() const {
return n - cur_idx();
}
unsigned short cur_sum() const {
return sum[cur_len()];
}
const vector<char>& possible_char() const {
const static vector<char> all{ 'a','b','c' };
const static vector<char> no_a{ 'b','c' };
const static vector<char> no_b{ 'a','c' };
const static vector<char> no_c{ 'a','b' };
if (cur_idx() == 0) {
return all;
}
auto back = determined.back();
if (back == 'a') {
return no_a;
}
else if (back == 'b') {
return no_b;
}
return no_c;
}
public:
string getHappyString(int n, int k) {
// init variables
this->n = n;
this->k = k;
determined.clear();
offset = 0;
bool find;
while (valid_offset(offset) && cur_idx() < n) {
const auto& ch_list = possible_char();
find = false;
for (const auto& ch : ch_list) {
if (valid_offset(offset + cur_sum())) {
offset += cur_sum();
continue;
}
find = true;
determined.push_back(ch);
break;
}
if (!find) {
return "";
}
}
string ans;
for (const auto& ch : determined) {
ans.push_back(ch);
}
return ans;
}
};