Find the String
Given two integer N and K. The task is to find the string S of minimum length such that it contains all possible strings of size N as a substring. The characters of the string can be from 0 to K-1.
Time : O(k^n)
Space : O(k^n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { unordered_map<string, vector<string>> adj; void initAdj (string& s, int p, int k) { if (p == s.length ()) adj[s] = {}; else { for (int i = 0 ; i < k; i++) { s[p] = (i | 0b110000 ); initAdj (s, p + 1 , k); } } } vector<string> buildEdges (string& key, int k) { string postfix = key.substr (1 ); vector<string> res; for (int i = 0 ; i < k; i++) { postfix.push_back (i | 0b110000 ); if (postfix != key) res.push_back (postfix); postfix.pop_back (); } return res; } void buildAdj (int k) { for (auto entity : adj) { string key = entity.first; adj[key] = buildEdges (key, k); } } public : string findString (int n, int k) { initAdj (string () = string (n, '#' ), 0 , k); buildAdj (k); string res (n, '0' ) ; string u = res; unordered_set<string> vis{u}; while (!adj[u].empty ()) { while (!adj[u].empty () and vis.count (adj[u].back ())) adj[u].pop_back (); if (adj[u].empty ()) break ; string v = adj[u].back (); adj[u].pop_back (); vis.insert (v); res.push_back (v.back ()); u = v; } return res; } };