String Hashing + Binary Search to find longest match
\nfrom collections import defaultdict\n\nclass SHash:\n    def __init__(self, input_string: str):\n        self.input_string = input_string\n        self.prime1
```\nfrom collections import defaultdict\n\nclass SHash:\n    def __init__(self, input_string: str):\n        self.input_string = input_string\n        self.prime1 = 31\n        self.prime2 = 37\n        self.mod1 = 10**9 + 7\n        self.mod2 = 10**9 + 9\n        self.precompute_hashes()\n        \n    def precompute_hashes(self):\n        n = len(self.input_string)\n        self.hash1 = [0] * (n + 1)\n        self.hash2 = [0] * (n + 1)\n        self.pow1 = [1] * (n + 1)\n        self.pow2 = [1] * (n + 1)\n        \n        for i in range(n):\n            self.hash1[i + 1] = (self.hash1[i] * self.prime1 + ord(self.input_string[i])) % self.mod1\n            self.hash2[i + 1] = (self.hash2[i] * self.prime2 + ord(self.input_string[i])) % self.mod2\n            self.pow1[i + 1] = (self.pow1[i] * self.prime1) % self.mod1\n            self.pow2[i + 1] = (self.pow2[i] * self.prime2) % self.mod2\n            \n    def hash(self, start: int, end: int):\n        hash_val1 = (self.hash1[end + 1] - self.hash1[start] * self.pow1[end - start + 1]) % self.mod1\n        hash_val2 = (self.hash2[end + 1] - self.hash2[start] * self.pow2[end - start + 1]) % self.mod2\n        \n        return (hash_val1, hash_val2)\n    \nclass SegmentTree:\n    def __init__(self, data, default=float(\'inf\'), func=min):\n        self._default = default\n        self._func = func\n        self._len = len(data)\n        self._size = _size = 1 << (self._len - 1).bit_length()\n\n        self.data = [default] * (2 * _size)\n        self.data[_size:_size + self._len] = data\n        for i in reversed(range(_size)):\n            self.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n    def __delitem__(self, idx):\n        self[idx] = self._default\n\n    def __getitem__(self, idx):\n        return self.data[idx + self._size]\n\n    def __setitem__(self, idx, value):\n        idx += self._size\n        self.data[idx] = value\n        idx >>= 1\n        while idx:\n            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n            idx >>= 1\n\n    def __len__(self):\n        return self._len\n\n    def query(self, start, stop):\n        start += self._size\n        stop += self._size\n\n        res_left = res_right = self._default\n        while start < stop:\n            if start & 1:\n                res_left = self._func(res_left, self.data[start])\n                start += 1\n            if stop & 1:\n                stop -= 1\n                res_right = self._func(self.data[stop], res_right)\n            start >>= 1\n            stop >>= 1\n\n        return self._func(res_left, res_right)\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n        dp = SegmentTree([float(\'inf\')] * (n + 1))\n        dp[n] = 0\n        groups = defaultdict(set)\n        for w in words:\n            shash = SHash(w)\n            m = len(w)\n            for l in range(1, m + 1):\n                groups[l].add(shash.hash(0, l - 1))\n        shash = SHash(target)\n        for i in range(n - 1, -1, -1):\n            beg = 1\n            end = n - i\n            while beg <= end:\n                mid = (beg + end) // 2\n                if shash.hash(i, i + mid - 1) in groups[mid]:\n                    beg = mid + 1\n                else:\n                    end = mid - 1\n            if beg - 1 > 0:\n                dp[i] = min(dp[i], 1 + dp.query(i + 1, i + beg))\n        if dp[0] == float(\'inf\'):\n            return -1\n        return dp[0]\n```
['Python']