16. Find the String

The problem can be found at the following link: Question Link

Solution Recommendation

At first glance I was not able to solve this question on my own then, on search I found that this question is a standard De Bruijn sequence.

For a clear explanation, I strongly recommend checking out this GFG article.

Time and Auxiliary Space Complexity

• Time Complexity: O(k^n), where k is the number of choices for each character and n is the size of substring.

• Auxiliary Space Complexity: O(k^n*n), due to the set storing visited nodes in set seen.

Code (C++)

class Solution {
public:
    void dfs(int k, string prev, unordered_set<string> &seen, string &edges) {
        for (char i = '0'; i <= ('0' + k - 1); i++) {
            string cur = prev + i;
            if (seen.find(cur) == seen.end()) {
                seen.insert(cur);
                dfs(k, cur.substr(1), seen, edges);
                edges += i;
            }
        }
    }

    string findString(int n, int k) {
        unordered_set<string> seen;
        string startingNode = string(n - 1, '0');
        string edges;
        dfs(k, startingNode, seen, edges);

        string ret = edges + startingNode;
        return ret;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.