💠  Rolling Greedy Polynomial Hashing Explanation - II
Intro \nThis problem is about breaking a target string into valid substrings, where each substring must match a prefix of some word in a list. After trying ever
# Intro \nThis problem is about breaking a target string into valid substrings, where each substring must match a prefix of some word in a list. After trying everything I moved towards efficient prefix checking, and a rolling hash approach. Hashing allows us to quickly verify if a substring matches any valid prefix in the word list.\n\n# Approach\n1. **Hashing Words:** \n   - First, precompute the rolling hash values for all prefixes of each word in the `words` list. Using a polynomial rolling hash function with a prime modulus and random base ensures minimal hash collisions.\n   - These hash values are stored in a set for fast lookups.\n\n2. **Hashing Target:**\n   - Next, compute the rolling hash for every prefix of the `target` string. This allows us to efficiently calculate the hash for any substring in constant time.\n\n3. **Greedy Splitting:**\n   - Then try to split the target string into the maximum possible number of valid substrings. For each position in the target string, we use a sliding window approach and binary search to find the farthest valid substring that matches any prefix hash from the words.\n   - If a valid substring is found, we advance the window and continue the process. If no valid substring can be found, it\u2019s impossible to fully split the target, and we return `-1`.\n\n# Complexity\n- **Time complexity:** \n  - Precomputing the hash values for each word and the target string takes $$O(m \\times k + n)$$ where:\n    - $$m$$ is the number of words.\n    - $$k$$ is the average length of a word.\n    - $$n$$ is the length of the target string.\n  - For each valid split attempt, we do binary search, making the overall complexity approximately $$O(n \\log n)$$ in the worst case.\n  \n  Hence, the total complexity is roughly $$O(m \\times k + n \\log n)$$.\n\n- **Space complexity:**\n  - Storing the hash values for prefixes of each word and the target string takes $$O(m \\times k + n)$$.\n\n# Code\n```python3 []\n# Weelky Q4 - Minimum Number of Valid Strings to Form Target II\n\n# set up --> base value & modulo for polynomial rolling hash\npw = random.randint(100, 200)  # base --> hashing\nmod = random.getrandbits(40)    # large prime-  like mod to avoid collisions\n\n# precompute powers of pw modulo mod\npowers = [1]\nfor _ in range(10**5):\n    powers.append(powers[-1] * pw % mod)\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)  # len of target string\n\n        # S1: precompute hash values for -- all prefixes of every word in \'words\'\n        word_hashes = set()  # set to store all possible hash values for word prefixes\n        for word in words:\n            current_hash = 0\n            for char in word:\n                # calc rolling hash for each prefix of the word\n                current_hash = (current_hash * pw + ord(char)) % mod\n                word_hashes.add(current_hash)  # store hash of the current prefix\n\n        # S2: precompute prefix hashes for -- target string\n        target_hashes = [0]  # target_hashes[i] will store hash of target[:i]\n        for char in target:\n            # compute rolling hash for each prefix of the target\n            target_hashes.append((target_hashes[-1] * pw + ord(char)) % mod)\n\n        # S3: greedily split target into max number of valid substrings\n        left = right = 0  # L n R pointers for current window in the target\n        split_count = 0    # counter for the num of valid substrings used\n        \n        while right < n:  # while --> haven\'t reached the end of the target string\n            max_right = right  # this will track the farthest we can extend the current valid substring\n            \n            # try to extend the substring from each starting point between L and R\n            for i in range(left, right + 1):\n                low, high = i, n - 1\n                # binary search for the farthest valid substring starting at index `i`\n                while low <= high:\n                    mid = (low + high) // 2\n                    # calc the hash for the substring target[i:mid+1]\n                    current_hash = (target_hashes[mid + 1] - target_hashes[i] * powers[mid + 1 - i] % mod) % mod\n                    if current_hash in word_hashes:\n                        low = mid + 1  # valid substring found, try to extend further\n                    else:\n                        high = mid - 1  # invalid, shrink the window\n\n                # update max_right --> farthest valid match found\n                max_right = max(max_right, high + 1)\n\n            # if no extension is possible, target cannot be fully split into valid words\n            if max_right == right:\n                return -1\n\n            # move the window forward to the next unmatched part of the target\n            left, right = right + 1, max_right\n            split_count += 1  # used one valid substring to cover part of the target\n        \n        return split_count  # finally\n\n```
['Math', 'Greedy', 'Rolling Hash', 'Python3']