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)

c++

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;
    }
};