Explained Aho-Corasick + greedy, 61ms beat 100%
Here\'s a concise description of the solution, focusing on the key invariants:\n\n# Intuition\nAho-Corasick algorithm can efficiently find, for each position in
Here\'s a concise description of the solution, focusing on the key invariants:\n\n# Intuition\nAho-Corasick algorithm can efficiently find, for each position in the target string, the longest preceding substring that is a valid prefix of a word in words.\n\n# Approach\nThe main steps of the approach are:\n\n1. **Construct the Aho-Corasick Trie**:\n   - The trie structure represents all the words in the `words` array.\n   - The `fail` pointers form a directed acyclic graph (DAG) that allows efficient traversal of the trie.\n\n2. **Compute the Longest Indexed Suffix**: Using the constructed trie, the solution computes the length of the longest valid preceding substring for each index in the target string.\n\n3. **Determine the Minimum Number of Valid Strings**:\nThe solution uses a greedy approach. The key insight is that the minimum number of valid strings required can be computed by iterating through the target string from right to left and subtracting the length of the longest valid prefix that ends at each position.\n\nSpecifically, the solution does the following:\n\n1. Iterate through the target string from right to left.\n2. At each index `i`, the length of the longest valid prefix that ends at that index is given by `lis[i]`. \n3. If `lis[i]` is 0, it means there is no valid prefix that can be used to form the target string, so the solution returns -1 (indicating it\'s not possible to form the target).\n4. Otherwise, the solution subtracts `lis[i]` from the current index `i`, and increments the count of valid strings required.\n\nThis greedy approach is optimal because if there were a more optimal solution that requires fewer valid strings, then there must be some rightmost position in the target string where the two solutions differ. At that position, the non-greedy solution would have a longer valid prefix than the greedy solution, which would contradict the optimality of the non-greedy solution.\n\n# Complexity\n- Time complexity: $$O(|target|)$$\n  - The time complexity of this final step is linear in the length of the target string, as it performs a single pass through the target string and performs constant-time operations at each index.\n\n- Space complexity: $$O(|target|)$$\n  - The space required is proportional to the length of the target string, as it uses the `lis` vector computed in the previous step.\n\n# Complexity\n- Time complexity: $$O(|target| + \\sum_{w \\in words} |w|)$$\n  - The time to construct the Aho-Corasick trie is $$O(\\sum_{w \\in words} |w|)$$.\n  - The time to compute the longest indexed suffix is $$O(|target|)$$.\n\n- Space complexity: $$O(\\sum_{w \\in words} |w|)$$\n  - The space required to store the Aho-Corasick trie is proportional to the total length of all the words in the `words` array.\n\n# Code\n```cpp []\nclass CarassiusTrie {\nprivate:\n    /** The Aho-Corasick algorithm maintains two key invariants:\n      * 1. The trie structure represents all the words in the `words` array.\n      * 2. The `fail` pointers that allows efficient traversal of the trie. */\n    struct Node {\n        Node** child = nullptr;\n        Node* fail = nullptr;\n        int len;\n        Node(int len = 0) : len(len) {}\n        Node* set_len(int len) {\n            this->len = len;\n            return this;\n        }\n        Node* operator[] (char c, vector<Node>& buf, int& nxb) {\n            if (!child[c])\n                child[c] = buf[nxb++].set_len(len + 1);\n            return child[c];\n        }\n    };\n\npublic:\n    CarassiusTrie(const vector<string>& words, const string& target)\n            : buf(accumulate(words.begin(), words.end(), 1,\n                                [](int acc, const string& s) { return acc + s.length(); })) {\n        minch = numeric_limits<char>::max();\n        char maxch = numeric_limits<char>::min();\n        for (char c : target) {\n            minch = min(minch, c);\n            maxch = max(maxch, c);\n        }\n        for (const string& w : words) for (char c : w) {\n            minch = min(minch, c);\n            maxch = max(maxch, c);\n        }\n        alp_size = maxch - minch + 1;\n        child_buf.resize(alp_size * buf.size());\n        for (int i = 0; i < buf.size(); ++i)\n            buf[i].child = &child_buf[i * alp_size];\n\n        root = &buf[nxb++];\n        for (const string& w : words)\n            index(w);\n        populate_fail();\n    }\n\n    vector<int> compute_longest_indexed_suffix(const string& t) {\n        const int L = t.length();\n        vector<int> lis(L);\n        transform(\n            t.begin(), t.end(), lis.begin(),\n            [n = this->root, this](char c) mutable {\n                c -= minch;\n                while (n != this->root && !n->child[c])\n                    n = n->fail;\n                if (n->child[c])\n                    n = n->child[c];\n                return n->len;\n            });\n        return lis;\n    }\n\nprivate:\n    Node* root;\n\n    vector<Node> buf;\n    int nxb = 0;\n\n    char minch;\n    int alp_size;\n    vector<Node*> child_buf;\n\n    void index(const string& t) {\n        Node* n = root;\n        for (char c : t)\n            n = (*n)[c - minch, buf, nxb];\n    }\n\n    void populate_fail() {\n        root->fail = root;\n        queue<Node*> q;\n        for (char c = 0; c < alp_size; ++c) if (root->child[c]) {\n            root->child[c]->fail = root;\n            q.push(root->child[c]);\n        }\n        while (!q.empty()) {\n            Node* n = q.front();\n            q.pop();\n            for (char c = 0; c < alp_size; ++c) if (n->child[c]) {\n                Node* f = n->fail;\n                while (f != root && !f->child[c])\n                    f = f->fail;\n                n->child[c]->fail = f->child[c] ? f->child[c] : root;\n                q.push(n->child[c]);\n            }\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int minValidStrings(const vector<string>& words, const string& target) {\n        CarassiusTrie caras(words, target);\n        const vector<int> lis(caras.compute_longest_indexed_suffix(target));\n        int res = 0;\n        for (int l = target.length(); l > 0;) {\n            if (lis[l - 1] == 0) return -1;\n            l -= lis[l - 1];\n            ++res;\n        }\n        return res;\n    }\n};\n\n```
['C++']