de Bruijn Sequence (Graph Theory) - GOOGLE INTERVIEW QUESTION

❗❗ASKED BEFORE ON A GOOGLE CODING INTERVIEW❗❗

this is a prefatory video on de Bruijn sequences, which are super cool strings that exhibit a special property. you might also be wondering what does graph theory have to do with this special sequence of characters. find out more by watching the video!

0:00 - Motivation Behind Video
0:41 - Formal Definition of a de Bruijn Sequence
1:15 - Example of a base-2 de Bruijn Sequence with substring size N=2
4:13 - Example of a base-2 de Bruijn Sequence with substring size N=3
6:16 - Additional Info
7:15- Example of a base-3 de Bruijn Sequence with substring size N=2
8:43 - GOOGLE CODING INTERVIEW QUESTION
9:24 - Algorithm Solution
10:48 - Algorithm Example Walkthrough
17:00 - C++ Code Explanation

[lambar]

Thanks …nice explanation … good one to develop proper intuition

[Avighna]

The thing is, this has really bad time complexity. There are 2^n nodes, and finding a hamiltonian path takes 2^N time, so the total time complexity is 2^2^n, which doesn't even run for n=6.

[juanete]

When do we need to use de Brijn and when Needleman-Wunsch?

[Shubh]

class Solution
{
public:

unordered_set<string> hash;
string ans;
int k;

void dfs(string u) {
for (int i = 0; i < k; i++) {
auto e = u + to_string(i);
if (!hash.count(e)) {
hash.insert(e);
dfs(e.substr(1));
ans += to_string(i);
}
}
}

string findString(int n, int _k) {
// code here
k = _k;
string start(n - 1, '0');
dfs(start);
string res = ans + start;
reverse(res.begin(), res.end());
return res;
}
};

[mantrarajgotecha]

Can you give a proof that, why always answer exists with this approach?