Easy Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\npw = random.randint(100, 200)\nmod = random.getrandbits(40)\n\npws = [1]\nfor _ in range(10 ** 5):\n    pws.append(pws[-1] * pw % mod)\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n        \n        vis = set()\n        for w in words:\n            x = 0\n            for c in w:\n                x = (x * pw + ord(c)) % mod\n                vis.add(x)\n        \n        acc = [0]\n        for c in target:\n            acc.append((acc[-1] * pw + ord(c)) % mod)\n        \n        l = r = 0\n        cnt = 0\n        while r < n:\n            nr = r\n            for i in range(l, r + 1):\n                left, right = i, n - 1\n                while left <= right:\n                    mid = (left + right) // 2\n                    if (acc[mid+1] - acc[i] * pws[mid+1-i] % mod) % mod in vis:\n                        left = mid + 1\n                    else:\n                        right = mid - 1\n                if right + 1 > nr:\n                    nr = right + 1\n                mid = right\n            if nr == r: return -1\n            l, r = r + 1, nr\n            cnt += 1\n        return cnt\n        \n```
['Python3']