<commit_before>// Time:  O(k^n)
// Space: O(k^n)

// https://en.wikipedia.org/wiki/De_Bruijn_sequence
class Solution {
public:
    string crackSafe(int n, int k) {
        const int M = pow(k, n - 1);
        vector<int> P;
        for (int i = 0; i < k; ++i) {
            for (int q = 0; q < M; ++q) {
                P.emplace_back(q * k + i);
            }
        }
        const int total = pow(k, n);
        string result(n - 1, '0' + k - 1);
        for (int i = 0; i < total; ++i) {
            int j = i;
            while (P[j] >= 0) {
                result.push_back('0' + j / M);
                auto Pj = P[j];
                P[j] = -1;
                j = Pj;
            }
        }
        return result;
    }
};

// Time:  O(n * k^n)
// Space: O(n * k^n)
class Solution2 {
public:
    string crackSafe(int n, int k) {
        string result(n, '0' + k - 1);
        unordered_set<string> lookup;
        lookup.emplace(result);
        const int total = pow(k, n);
        while (lookup.size() < total) {
            auto node = result.substr(result.length() - n + 1);
            for (int i = 0; i < k; ++i) {
                auto neighbor = node;
                neighbor.push_back('0' + i);
                if (!lookup.count(neighbor)) {
                    lookup.emplace(neighbor);
                    result.push_back('0' + i);
                    break;
                }
            }
        }
        return result;<commit_msg>Update cracking-the-safe.cpp<commit_after>// Time:  O(k^n)
// Space: O(k^n)

// https://en.wikipedia.org/wiki/De_Bruijn_sequence
class Solution {
public:
    string crackSafe(int n, int k) {
        const int M = pow(k, n - 1);
        vector<int> P;
        for (int i = 0; i < k; ++i) {
            for (int q = 0; q < M; ++q) {
                P.emplace_back(q * k + i);
            }
        }
        const int total = pow(k, n);
        string result(n - 1, '0' + k - 1);
        for (int i = 0; i < total; ++i) {
            int j = i;
            while (P[j] >= 0) {
                result.push_back('0' + j / M);
                auto Pj = P[j];
                P[j] = -1;
                j = Pj;
            }
        }
        return result;
    }
};

// Time:  O(n * k^n)
// Space: O(n * k^n)
class Solution2 {
public:
    string crackSafe(int n, int k) {
        string result(n, '0' + k - 1);
        unordered_set<string> lookup;
        lookup.emplace(result);
        const int total = pow(k, n);
        while (lookup.size() < total) {
            auto node = result.substr(result.length() - n + 1);
            for (int i = 0; i < k; ++i) {
                const auto& neighbor = node + to_string(i);
                if (!lookup.count(neighbor)) {
                    lookup.emplace(neighbor);
                    result.push_back('0' + i);
                    break;
                }
            }
        }
        return result;
{'fraction_non_alphanumeric': 0.15130674002751032, 'fraction_numerical': 0.011348005502063274, 'mean_word_length': 1.2071320182094083, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6781886', 'n_tokens_mistral': 1011, 'n_tokens_neox': 964, 'n_words': 260}