Hashing || Binary Search || Segment Tree || Lazy Propagation
Approach\nthere are following things which need to be done here:\n1. String matching with polynomial Hashing.\n2. Lazy Propagation for Range Minimum Query.\n3. 
# Approach\nthere are following things which need to be done here:\n1. String matching with polynomial Hashing.\n2. Lazy Propagation for Range Minimum Query.\n3. Binary Search.\n\n\nLets start with the String Matching code.\nHere I create a class were we are gonna check whether the substring of target matches with any prefix present in the array of strings \'words\'.\nFirstly create hash value of all prefix of each string in words and store it in a unordered_map and check wheather the hash value of a given substring of target present into that map or not.\n \nNow coming to the binary search part.\nIf I\'m on the ith index then will find the largest index till when prefix present suppose that index is j.\n\nThen for each index between [i, j] I will update each of with 1 + (minimum number of valid strings that can be concatenated till index (i - 1)).\n\nAnd finally return minimum value at n - 1.\n\n# Complexity\n- Time complexity:\nHashingTime = min(n, words[i] * words[i].size());\noverall = min(n * logn, HashingTime)\n\n# Code\n```cpp []\nconst int inf = 2e9;\nclass Hashing{\n    long long p;\n    int N, mod, length;\n    vector<long long> power;\n    vector<long long> hashString;\n    unordered_map<long long, bool> hashPresent;\npublic:\n    Hashing(){}\n    Hashing(int N, int length, int mod, long long p) {\n        this-> p = p;\n        this-> N = N;\n        this-> mod = mod;\n        this->length = length;\n        power.resize(N + 1);\n        hashString.resize(length + 1);\n    }\n    void init(string& s, vector<string> words) {\n        power[0] = 1;\n        for(int i = 1; i <= N; i++) {\n            power[i] = (power[i - 1] % mod * p % mod) % mod;\n        }\n        for(int i = 1; i <= length; i++) {\n            hashString[i] = (hashString[i - 1] % mod + (power[i] * 1LL * (s[i - 1] - \'a\' + 1)) % mod) % mod;\n        }\n        for(int i = 0; i < words.size(); i++) {\n            string temp = words[i];\n            long long hashValue = 0;\n            for(int i = 1; i <= (int) temp.size(); i++) {\n                hashValue = (hashValue % mod + power[i] * 1LL * (temp[i - 1] - \'a\' + 1) % mod) % mod;\n                hashPresent[(hashValue % mod * power[N] % mod) % mod] = true;\n            }\n        }\n    }\n    bool foundString(int i, int j) {\n        long long hash = ((hashString[j + 1] - hashString[i] + mod) % mod * power[N - i] % mod) % mod;\n        return (hashPresent.find(hash) != hashPresent.end());\n    }\n};\n\nclass SegmentTree {\n    int n;\n    vector<int> seg, lazy;\n    \n    void propagate(int ind, int st, int en) {\n        if (lazy[ind] != inf) {\n            seg[ind] = min(seg[ind], lazy[ind]);\n            \n            if (st != en) { \n                lazy[2 * ind + 1] = min(lazy[2 * ind + 1], lazy[ind]);\n                lazy[2 * ind + 2] = min(lazy[2 * ind + 2], lazy[ind]);\n            }\n            \n            lazy[ind] = inf;\n        }\n    }\n    \npublic:\n    SegmentTree(int _n) : n(_n) {\n        seg.resize(4 * n, inf);\n        lazy.resize(4 * n, inf);\n    }\n    \n    void rangeUpdate(int ind, int st, int en, int l, int r, int val) {\n        propagate(ind, st, en);\n        \n        if (st > r || en < l) return;\n        \n        if (st >= l && en <= r) {\n            lazy[ind] = min(lazy[ind], val);\n            propagate(ind, st, en);\n            return;\n        }\n        \n        int mid = (st + en) >> 1;\n        rangeUpdate(2 * ind + 1, st, mid, l, r, val);\n        rangeUpdate(2 * ind + 2, mid + 1, en, l, r, val);\n        \n        seg[ind] = min(seg[2 * ind + 1], seg[2 * ind + 2]);\n    }\n    \n    int query(int ind, int st, int en, int l, int r) {\n        if (st > r || en < l) return inf;\n        \n        propagate(ind, st, en);\n        \n        if (st >= l && en <= r) {\n            return seg[ind];\n        }\n        \n        int mid = (st + en) >> 1;\n        return min(query(2 * ind + 1, st, mid, l, r), query(2 * ind + 2, mid + 1, en, l, r));\n    }\n    \n    void update(int l, int r, int val) {\n        rangeUpdate(0, 0, n - 1, l, r, val);\n    }\n    \n    int query(int l, int r) {\n        return query(0, 0, n - 1, l, r);\n    }\n};\n\nclass Solution {\npublic:\n    const static int N = 1e5;\n    Hashing* hasher1;\n    Hashing* hasher2;\n    int minValidStrings(vector<string>& words, string target) {\n        int n = target.size();\n        hasher1 = new Hashing(N, n, 1e9 + 7, 29);\n        hasher2 = new Hashing(N, n, 1e9 + 9, 31);\n        hasher1->init(target, words);\n        hasher2->init(target, words);\n        \n        SegmentTree S(n);\n        \n        for(int i = 0; i < n; i++) {\n            int index = -1;\n            int l = i, h = n - 1;\n            while(l <= h) {\n                int mid = (l + h) >> 1;\n                if(hasher1->foundString(i, mid) && hasher2->foundString(i, mid)) {\n                    index = mid;\n                    l = mid + 1;\n                }\n                else {\n                    h = mid - 1;\n                }\n            }\n            if(index == -1) continue;\n            int minTillNow = (i == 0 ? 0 : S.query(i - 1, i - 1));\n            S.update(i, index, minTillNow + 1);\n        }\n        int result = S.query(n - 1, n - 1);\n        delete hasher1;\n        delete hasher2;\n        return (result == inf ? -1 : result);\n    }\n};\n```
['Binary Search', 'Segment Tree', 'Rolling Hash', 'C++']