[Greedy] String Hashing + Binary Search + Segment Tree. Passes both easy and hard versions.
Intuition\n- Greedy strategy works: Take the longest suffix of target which is also a prefix of some word and continue the process.\n\n- Example:\n  - words = [
# Intuition\n- Greedy strategy works: Take the longest suffix of `target` which is also a prefix of some `word` and continue the process.\n\n- Example:\n  - `words = ["abc","aaaaa","bcdef"], target = "aabcdabc"`\n  - `abc` is longest suffix from `target` which is also a prefix.\n`target` now becomes `aabcd`.\n  - `bcd` is longest suffix from `target` which is also a prefix.\n`target` now becomes `aa`.\n  - `aa` is longest suffix from `target` which is also a prefix.\n`target` now becomes `""`.\n  - Thus, the answer is 3. You can easily prove that this greedy strategy always gives us the best answer.\n\n# Approach\n- `n` is the length of `target`.\n- `m` is the size of the words array.\n- `w` is the maximum word length of any word in the array.\n- Use double base primes for string hashing.\n\n## Step by step solving this problem:\n  - Generate hash values for all prefixes of all words.\n  - Generate hash values for all prefixes of `target`.\n  - Now, for every `i` from `0` to `n - 1`, find the maximum index from `i` such that the substring in `[i, idx]` is valid (basically the longest substring starting from i, which is a valid substring).\n`ending_index = idx, starting_index = i`.\n  - Store these `(ending_index, starting_index)` pairs in a set of pairs.\nLet the size of the set of pairs be `N`.\n  - Sort them in ascending order by the ending_index.\n  - Build a Segment Tree based on the starting indices.\nThis helps in finding the `min_starting_index` whose `end_index is >= idx `\n( for some index `idx`).\n\n  - Now, we can start finding the longest suffix which is also a prefix.\n  - To do that, find the first index in `end_indices` that is `>=` our current string\'s end index (which is `R`). Call it `idx`.\n  - Now check if `idx` exists. If it doesn\'t, return -1.\n  - Query the Segment Tree in range `[idx, N - 1]` to find the `min_starting_index`.\n  - Check if the `min_starting_index is <= R`. If not, return -1.\n  - If everything\'s good, we have successfully found the longest prefix which is also a suffix. Now set `R to min_starting_index - 1` and continue the process. \n# Complexity\n- Time complexity:\n`O(n.log(n).log(n))`\n\n- Space complexity:\n`O(n)`\n\n# Code\n```cpp []\n#include <iostream>\n#include <cstdlib>\n#include <ctime>\n#include <climits>\n#include <numeric>\n#include <iomanip>\n#include <fstream>\n#include <string>\n#include <algorithm>\n#include <cmath>\n#include <bitset>\n#include <utility>\n#include <array>\n#include <vector>\n#include <deque>\n#include <forward_list>\n#include <list>\n#include <set>\n#include <unordered_set>\n#include <map>\n#include <unordered_map>\n#include <stack>\n#include <queue>\n#include <functional>\n#include <random>\n#include <chrono>\n#include <ranges>\n#include <ext/pb_ds/assoc_container.hpp>\n\nusing namespace __gnu_pbds;\ntemplate <typename T>\nusing ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;\ntemplate <typename T>\nusing ordered_multiset = tree<std::pair<T, T>, null_type, std::less<std::pair<T, T>>, rb_tree_tag, tree_order_statistics_node_update>;\n\nusing ll = long long;\nusing ld = long double;\nusing namespace std;\n\npair<ll, ll> extended_euclidean(ll a, ll b)\n{\n    if (b == 0)\n    {\n        return {1, 0};\n    }\n\n    auto [x, y] = extended_euclidean(b, a % b);\n\n    return {y, x - y * (a / b)};\n}\n\nll modinv(ll a, ll m)\n{\n    ll x = extended_euclidean(a, m).first;\n\n    return (x % m + m) % m;\n}\n\nclass SegmentTree\n{\nprivate:\n    ll n;\n    vector<ll> tree;\n\n    void build(vector<ll> &arr, ll u, ll l, ll r)\n    {\n        if (l == r)\n        {\n            tree[u] = arr[l];\n        }\n\n        else\n        {\n            ll mid = (l + r) / 2;\n            build(arr, 2 * u, l, mid);\n            build(arr, 2 * u + 1, mid + 1, r);\n            tree[u] = min(tree[2 * u], tree[2 * u + 1]);\n        }\n    }\n\npublic:\n    SegmentTree(vector<ll> &arr)\n    {\n        n = (ll)arr.size();\n        tree.resize(4 * n);\n\n        if (n != 0)\n        {\n            build(arr, 1, 0, n - 1);\n        }\n    }\n\n    ll query(ll ql, ll qr, ll l = 0, ll r = -1, ll u = 1)\n    {\n        if (r == -1)\n        {\n            r = n - 1;\n        }\n\n        if (l == ql && r == qr)\n        {\n            return tree[u];\n        }\n\n        else\n        {\n            ll mid = (l + r) / 2;\n\n            if (ql >= l && qr <= mid)\n            {\n                return query(ql, qr, l, mid, 2 * u);\n            }\n\n            else if (ql >= mid + 1 && qr <= r)\n            {\n                return query(ql, qr, mid + 1, r, 2 * u + 1);\n            }\n\n            else\n            {\n                return min(query(ql, mid, l, mid, 2 * u), query(mid + 1, qr, mid + 1, r, 2 * u + 1));\n            }\n        }\n    }\n};\n\nclass Solution\n{\npublic:\n    int minValidStrings(vector<string> &words, string target)\n    {\n        ll n = (ll)target.length();\n        const ll p1 = 31;\n        const ll p2 = 37;\n        const ll m = 1e9 + 7;\n\n        vector<ll> p1_pow(50000), p2_pow(50000);\n        p1_pow[0] = 1;\n        p2_pow[0] = 1;\n\n        for (ll i = 1; i < 50000; i++)\n        {\n            p1_pow[i] = (p1_pow[i - 1] * p1) % m;\n            p2_pow[i] = (p2_pow[i - 1] * p2) % m;\n        }\n\n        set<pair<ll, ll>> hashes;\n\n        for (auto &word : words)\n        {\n            ll hash_value1 = 0, hash_value2 = 0;\n\n            for (ll i = 0; i < (ll)word.size(); i++)\n            {\n                hash_value1 = (hash_value1 + (word[i] - \'a\' + 1) * p1_pow[i]) % m;\n                hash_value2 = (hash_value2 + (word[i] - \'a\' + 1) * p2_pow[i]) % m;\n                hashes.insert({hash_value1, hash_value2});\n            }\n        }\n\n        vector<ll> prefix_hash1(n), prefix_hash2(n);\n\n        for (ll i = 0; i < n; i++)\n        {\n            prefix_hash1[i] = (((i == 0) ? 0 : prefix_hash1[i - 1]) + (target[i] - \'a\' + 1) * p1_pow[i]) % m;\n            prefix_hash2[i] = (((i == 0) ? 0 : prefix_hash2[i - 1]) + (target[i] - \'a\' + 1) * p2_pow[i]) % m;\n        }\n\n        vector<pair<ll, ll>> pairs;\n\n        for (ll i = 0; i < n; i++)\n        {\n            ll low = i, high = n - 1;\n            ll end_idx = -1;\n\n            while (low <= high)\n            {\n                ll mid = (low + high) / 2;\n\n                ll hash_0_to_mid1 = prefix_hash1[mid];\n                ll hash_0_to_mid2 = prefix_hash2[mid];\n                ll hash_0_to_iminus11 = ((i == 0) ? 0 : prefix_hash1[i - 1]);\n                ll hash_0_to_iminus12 = ((i == 0) ? 0 : prefix_hash2[i - 1]);\n                ll p1_inv = modinv(p1_pow[i], m);\n                ll p2_inv = modinv(p2_pow[i], m);\n\n                ll hash_value1 = (((hash_0_to_mid1 - hash_0_to_iminus11 + m) % m) * p1_inv) % m;\n                ll hash_value2 = (((hash_0_to_mid2 - hash_0_to_iminus12 + m) % m) * p2_inv) % m;\n\n                if (hashes.contains({hash_value1, hash_value2}))\n                {\n                    low = mid + 1;\n                    end_idx = mid;\n                }\n\n                else\n                {\n                    high = mid - 1;\n                }\n            }\n\n            if (end_idx != -1)\n            {\n                pairs.emplace_back(end_idx, i);\n            }\n        }\n\n        ranges::sort(pairs);\n\n        vector<ll> end_idxs, start_idxs;\n\n        for (auto &[en, st] : pairs)\n        {\n            end_idxs.push_back(en);\n            start_idxs.push_back(st);\n        }\n\n        SegmentTree tree(start_idxs);\n        ll R = n - 1;\n        ll N = (ll)end_idxs.size();\n        ll ans = 0;\n\n        while (R >= 0)\n        {\n            auto it = lower_bound(end_idxs.begin(), end_idxs.end(), R);\n\n            if (it == end_idxs.end())\n            {\n                return -1;\n            }\n\n            ll idx = it - end_idxs.begin();\n            ll min_starting_point = tree.query(idx, N - 1);\n\n            if (min_starting_point > R)\n            {\n                return -1;\n            }\n\n            ans++;\n            R = min_starting_point - 1;\n        }\n\n        return ans;\n    }\n};\n\n```
['C++']