De Bruijn Sequence

De Bruijn Sequence is a binary sequence of order $ n $ of bits $b_i \in {0, 1} $ where $ b = {b_i, ..., b_{2^n}}$ such that every string of length $ n $ ${a_1, ..., a_n} \in $ {0, 1} $ ^ n $ occurs exactly once consecutively in $b$. To generate a De Bruijn Sequence, we need to get the Euler circuit for the graph for all $ n - 1 $ possible stringds. For example, given $ n = 4 $ & $ k = 2 $,  We would have a sequence of length $2 ^ 4 = 16$ using Eulerian $k$-D de Bruijn graph cycle where $k = n - 1$ which is 3 in this case. Each edge will be traversed exactly once to use each of the 16 4-digit sequences exactly once. The Eulerian path is $$ 000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000. $$ The de Bruijn sequence is $$ 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 $$ For output sequences of length $ k = 4 $, we got ``` {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... ``` To find Euler circuit, we can use Hierholzer’s algorithm to get it in linear time. If we randomly traverse the graph without repeating edges, it will eventually end up on the same vertex but the path may not include all the edges. Therefore, we have to remove those visited edges from the graph, which will split into several components. All the components contain Euler Circuit. ## [Cracking the Safe (Hard)](https://leetcode.com/problems/cracking-the-safe/) There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1]. The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit. For example, the correct password is "345" and you enter in "012345": After typing 0, the most recent 3 digits is "0", which is incorrect. After typing 1, the most recent 3 digits is "01", which is incorrect. After typing 2, the most recent 3 digits is "012", which is incorrect. After typing 3, the most recent 3 digits is "123", which is incorrect. After typing 4, the most recent 3 digits is "234", which is incorrect. After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks. What is the string of minimum length that will unlock the safe at some point of entering it? For example, $ n = 2, k = 2 $, one of the possible answers is $01100$ because we can type $01$ from the $1st$ digit, $11$ from the $2nd$ digit, $10$ from the $3rd$ digit, and $00$ from the $4th$ digit. ## Solution ```cpp class Solution { public: string ans; vector> vis; int n, k, v; void dfs(int u) { for(int i = 0; i < k; i++) { if(!vis[u][i]) { vis[u][i] = 1; dfs((u * k + i) % v); ans += '0' + i; } } } string crackSafe(int n, int k) { if(k == 1) return string(n, '0'); this->n = n, this->k = k; v = pow(k, n - 1); // vis[k ^ (n - 1)][k] vis.resize(v, vector(k)); dfs(0); return ans + ans.substr(0, n - 1); } }; ```