C, simple/short solution 185 ms w/ two pointer and rolling hash only
Let n = length of target, m = total length of words.\n\n# Intuition\nWe sort the list of prefix hashes of words in O(m * log m) time. This allows us to binary s
Let n = length of target, m = total length of words.\n\n# Intuition\nWe sort the list of prefix hashes of `words` in O(m * log m) time. This allows us to binary search in O(log m) time, for any `i, j`, whether `target[i..j]` is a word prefix (recall that hash of `target[i..j]` is updated in O(1) time when incrementing `i` or `j`).\n\n(note: a HashSet or Bloom filter could be used for the above step to get O(1) amortized average. but these are more tedious to tune from scratch in C)\n\nLet `dp[j]` be the solution for `target[..j]`. We use the greedy algorithm for `dp[j]`; that is, we take the longest word prefix `target[i..j]`. To see why this works, we need to understand why `target[k..j]` with `k > i` cannot be better. This is because any solution for `target[k:]` can be truncated to `target[i:]`.\n\nTo track `target[i..j]`, we can use two-pointer technique `i <= j`. This works since `target[i..j+1]` can only be a word prefix if `target[i..j]` is a word prefix, therefore we can increment `i` monotonically and it will always track the longest word prefix for `j`.\n\nFinally, `dp[j] = dp[i - 1] + 1` and the answer is `dp[-1]`.\n\n# Complexity\n- Time complexity: O((m + n) * log m)\n- Space complexity: O(n + m)\n\n# Code\n```c []\n#define M1 (1000000007LL)\n#define M2 (1000000009LL)\n#define P (31LL)\n\nint cmp_u128(const void *a, const void *b) {\n    const uint64_t *ua = (const uint64_t*)a;\n    const uint64_t *ub = (const uint64_t*)b;\n    \n    if (ua[0] < ub[0]) return -1;\n    if (ua[0] > ub[0]) return 1;\n    if (ua[1] < ub[1]) return -1;\n    if (ua[1] > ub[1]) return 1;\n    return 0;\n}\n\nint find_u128(uint64_t *arr, int n, uint64_t *h) {\n    int left = 0, right = n - 1;\n    while (left <= right) {\n        int mid = left + (right - left) / 2;\n        int cmp = cmp_u128(&arr[mid * 2], h);\n        if (cmp == 0) return mid;\n        if (cmp < 0) left = mid + 1;\n        else right = mid - 1;\n    }\n    return -1;\n}\n\nint minValidStrings(char** words, int wordsSize, char* target) {\n    uint64_t h[2] = {0}, l = 0, r = 0, nHashes = 0, n = strlen(target), m = 0;\n    for (int i = 0; i < wordsSize; i++) m += strlen(words[i]);\n    uint64_t p1[n + 1], p2[n + 1], prefixHashes[m * 2], dp[n];\n    for (int i = 0; i < wordsSize; i++) {\n        h[0] = h[1] = 0;\n        for (char *c = words[i]; *c; c++) {\n            h[0] = (h[0] * P + (*c - \'a\' + 1)) % M1;\n            h[1] = (h[1] * P + (*c - \'a\' + 1)) % M2;\n            prefixHashes[2 * nHashes] = h[0];\n            prefixHashes[2 * nHashes++ + 1] = h[1];\n        }\n    }\n    qsort(prefixHashes, nHashes, 2 * sizeof(uint64_t), cmp_u128);\n    h[0] = h[1] = 0;\n    p1[0] = p2[0] = 1;\n    for (char *c = target; *c; c++, r++) {\n        p1[r + 1] = (p1[r] * P) % M1;\n        p2[r + 1] = (p2[r] * P) % M2;\n        h[0] = (h[0] * P + (*c - \'a\' + 1)) % M1;\n        h[1] = (h[1] * P + (*c - \'a\' + 1)) % M2;\n        for (; find_u128(prefixHashes, nHashes, h) == -1; l++) {\n            if (l == r) return -1;\n            h[0] = (h[0] + (M1 - p1[r - l]) * (target[l] - \'a\' + 1)) % M1;\n            h[1] = (h[1] + (M2 - p2[r - l]) * (target[l] - \'a\' + 1)) % M2;\n        }\n        dp[r] = l == 0 ? 1 : 1 + dp[l - 1];\n    }\n    return r == 0 ? -1 : dp[r - 1];\n}\n```
['Two Pointers', 'Binary Search', 'Dynamic Programming', 'Greedy', 'C', 'Rolling Hash', 'Sorting']