2  Approaches with O(m + n) | dp[i] <= dp[j] for i <= j
Approach 1: Aho-Corasick + DP + Greedy\n## Idea\n- dp[i] stores the answer for target[...i]\n- Important observation: dp[i] <= dp[j] for i <= j\n  - Why ? Becau
# Approach 1: Aho-Corasick + DP + Greedy\n## Idea\n- `dp[i]` stores the answer for `target[...i]`\n- **Important observation**: `dp[i] <= dp[j] for i <= j`\n  - Why ? Because  `target[i...j]` is also a combination of prefixes of `words`.\n  - If this is not clear to you, @votrubac has a nice explanation in his [solution](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-ii/solutions/5788346/kmp). Please check it out.\n- So for each position `i`, we just need to find the longest suffix of `target[...i]` which is also a prefix of `words`. The Aho-Corasick algorithm on Trie allows us to do that.\n   - For more details about Aho-Corasick, see:\n        - [Aho-Corasick algorithm - Algorithms for Competitive Programming](https://cp-algorithms.com/string/aho_corasick.html)\n        - https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf \n   -  Basically, it is a general case of KMP on a set of patterns. \n\n## Complexity\n- Time complexity: $$O(m + n)$$\n  - $$O(m)$$ for building the trie with $$m$$ being the total words length\n  - $$O(n)$$ for calculating the dp with $$n$$ being the length of `target`\n\n- Space complexity: $$O(m + n)$$\n  - $$O(m)$$ for the trie\n  - $$O(n)$$ for the dp array \n  - The dp can be done in $$O(1)$$ space, making the overal space complexity $$O(m)$$. See below for details.\n\n![image.png](https://assets.leetcode.com/users/images/5bd4b817-5d0c-4bfb-9dff-cb5b12cf9313_1726430988.2301273.png)\n\n\n\n\n# Approach 2: Rolling Hash + Sliding Window + DP + Greedy\n## Idea\n- Same dp array as above.\n- **We make another important observation**: \n    - If the longest match for `dp[r]` starts from `l`\n    - then the longest match for `dp[r + 1]` cannot starts before `l`\n\n## Complexity\n- Time complexity: $$O(n + m)$$\n    - Compute the rolling hash for all possible prefix, this is $$O(m)$$\n    - Perform sliding window to find the longest postfix matched at each position, this is $$O(n)$$\n- Space complexity: $$O(m + n)$$\n    - $$O(m)$$ for storing all the prefix hashes\n    - $$O(n)$$ for the dp array\n    - The dp can be done in $$O(1)$$ space, making the overal space complexity $$O(m)$$. See below for details.\n\nNote: This takes significantly less space than approach 1, this could be that the Trie is expensive to store, or maybe it\'s just that my poor implementation of Aho-Corasick is poor.\n![image.png](https://assets.leetcode.com/users/images/bda7c7e8-b5ee-4c1b-8fc3-917d829268d4_1726508396.4178913.png)\n\n## An even faster implementation\nIf you don\'t like the `PolynomialRollingHash` class and want to implement rolling hash directly to get the best speed possible, I also got you covered. Please check the 3rd code tab.\n\n![image.png](https://assets.leetcode.com/users/images/85e3cb18-c68d-4aa1-be0a-0e6da78d1b7e_1726510332.4594128.png)\n\n# Making the space complexity O(m)\nAs suggested by @zsq007 in his [comment](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-ii/solutions/5788552/2-approaches-with-om-n-dpi-dpj-for-i-j/comments/2632054), the dp part can be done in $$O(1)$$ space.\n\nThe idea is, it\'s observed that the dp array would consists of spans of equal numbers, e.g. `1112222223444...`\n        \n=> So we can just keep track of when `l` moves to a new span, no need to store the whole dp array.\n\nThe code for rolling hash with $$O(m)$$ space is included in the 4th code tab. Note that this can also be applied for the Aho-Corasick approach, but I leave it as an excercise for the reader.\n\n\n\n# Code\n```python [AhoCorasick]\nclass AhoCorasick:\n    def __init__(self, patterns: List[str]):\n        self.trie = dict()\n        self.vocab = set(\'qwertyuiopasdfghjklzxcvbnm\')\n        root = self.trie\n        root[\'parent\'] = None\n        root[\'$\'] = 0 # len at root\n\n        # build the trie\n        for p in patterns:\n            cur = root\n            l = 0\n            for c in p:\n                if c not in cur:\n                    cur[c] = {\'parent\': cur}\n                cur = cur[c]\n                l += 1\n                # store the length at every prefix\n                cur[\'$\'] = l\n\n        # construct suffix\n        # refer to these materials for more details about AhoCorasick\n        # - https://cp-algorithms.com/string/aho_corasick.html\n        # - https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf \n        parent = None\n        root[\'suffix\'] = None\n        q = deque([root])\n        while q:\n            for _ in range(len(q)):\n                cur = q.popleft()\n                for c, child in cur.items():\n                    if c not in self.vocab:\n                        continue\n\n                    suffix = cur[\'suffix\']\n                    while suffix and c not in suffix:\n                        suffix = suffix[\'suffix\']\n                    if suffix:\n                        child[\'suffix\'] = suffix[c]\n                    else:\n                        child[\'suffix\'] = root\n\n                    q.append(child)\n\n\n    def match(self, target: str):\n        cur = self.trie\n        for c in target:\n            while c not in cur and cur[\'suffix\']:\n                cur = cur[\'suffix\']\n\n            if c in cur:\n                cur = cur[c]\n\n            # the first match that ends at each position (which is also the longest)\n            yield cur[\'$\']\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        trie = AhoCorasick(words)\n        \n        n = len(target)\n        i = 0\n        dp = [inf] * n + [0] # 0 at the end as the sentinel value\n        for m in trie.match(target):\n            # only consider the longest match\n            # because dp[i] <= dp[j] for i <= j\n            dp[i] = min(dp[i], dp[i - m] + 1)\n\n            # early stop when there can\'t be any match\n            if dp[i] == inf:\n                return -1\n            i += 1\n        \n        return dp[-2]\n```\n\n```python [Rolling Hash + Sliding Window]\nclass PolynomialRollingHash:\n    M = 10**9 + 9\n    P = 31 # 31, 53, 29791, 11111, 111111\n    P_INV = pow(P, M - 2, M)\n    POWS = [1]\n\n    def __init__(self, sequence=""):\n        self.sequence = deque()\n        self.hash = 0\n        for element in sequence:\n            self.append(element)\n\n    def get_pow(self, i) -> int:\n        while len(self.POWS) <= i:\n            self.POWS.append(self.POWS[-1] * self.P % self.M)\n\n        return self.POWS[i]\n\n    def encode(self, element) -> int:\n        """\n        Encode a single element\n\n        Note: avoid producing an encoding of 0.\n        E.g. a -> 0 then the hashes for a, aa, aaa, ... are all 0.\n        """\n\n        # for lower-cased str inputs\n        return ord(element) - 96\n\n    def appendleft(self, element) -> int:\n        x = self.encode(element)\n        p = self.get_pow(len(self.sequence))\n        self.sequence.appendleft(element)\n\n        self.hash = (x * p + self.hash) % self.M\n\n        return self.hash\n\n    def popleft(self) -> int:\n        element = self.sequence.popleft()\n        x = self.encode(element)\n        p = self.get_pow(len(self.sequence))\n\n        self.hash = (self.hash - x * p) % self.M\n\n        return self.hash\n\n    def append(self, element) -> int:\n        x = self.encode(element)\n        self.sequence.append(element)\n\n        self.hash = (self.hash * self.P + x) % self.M\n\n        return self.hash\n\n    def pop(self) -> int:\n        element = self.sequence.pop()\n        x = self.encode(element)\n\n        self.hash = ((self.hash - x) * self.P_INV) % self.M\n\n        return self.hash\n\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        # compute the hash for all prefix\n        prefixes = set()\n        for w in words:\n            hasher = PolynomialRollingHash()\n            for c in w:\n                hasher.append(c)\n                prefixes.add(hasher.hash)\n        \n        n = len(target)\n        dp = [inf] * n + [0] # 0 at the end as the sentinel value\n\n        """\n        Important observation:\n        \n        If longest match at dp[r] starts at l \n        then longest match at dp[r + 1] cannot starts before l\n\n        Thus a sliding window is applicable here.\n        """\n\n        l = 0\n        hasher = PolynomialRollingHash()\n        for r in range(n):\n            # expand the window one step to the right\n            hasher.append(target[r])\n\n            # shrink the window from the left until found a valid prefix\n            h = hasher.hash\n            while l <= r and h not in prefixes:\n                h = hasher.popleft()\n                l += 1\n\n            # early stop if no valid prefix found\n            if l > r:\n                return -1\n\n            # update the dp\n            dp[r] = dp[l - 1] + 1\n        \n        return dp[-2]\n```\n\n```python [Even faster]\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        p = 31 # 31, 53, 29791, 11111, 111111\n        M = 10**9 + 7\n        power = [1]\n\n        n = len(target)\n        for _ in range(n + 1):\n            power.append((power[-1] * p) % M)\n\n        # compute the hash for all prefix\n        prefixes = set()\n        for w in words:\n            m = len(w)\n            h = 0\n            for c in w:\n                h = (h * p + (ord(c) - 96)) % M\n                prefixes.add(h)\n        \n        dp = [inf] * n + [0] # 0 at the end as the sentinel value\n\n        """\n        Important observation:\n        \n        If longest match at dp[r] starts at l \n        then longest match at dp[r + 1] cannot starts before l\n\n        Thus a sliding window is applicable here.\n        """\n\n        h = 0\n        l = 0\n        for r in range(n):\n            # expand the window one step to the right\n            h = (h * p + (ord(target[r]) - 96)) % M\n\n            # shrink the window from the left until found a valid prefix\n            while l <= r and h not in prefixes:\n                x = ord(target[l]) - 96\n                h = (h - (x * power[r - l])) % M\n                l += 1\n\n            # early stop if no valid prefix found\n            if l > r:\n                return -1\n\n            # update the dp\n            dp[r] = dp[l - 1] + 1\n        \n        return dp[-2]\n```\n\n```python [O(m) space]\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        p = 53 # 31, 53, 29791, 11111, 111111\n        M = 10**9 + 7\n        power = [1]\n\n        n = len(target)\n        for _ in range(n + 1):\n            power.append((power[-1] * p) % M)\n\n        # compute the hash for all prefix\n        prefixes = set()\n        for w in words:\n            m = len(w)\n            h = 0\n            for c in w:\n                h = (h * p + (ord(c) - 96)) % M\n                prefixes.add(h)\n        \n\n        """\n        Important observation:\n        \n        - If longest match at dp[r] starts at l \n        then longest match at dp[r + 1] cannot starts before l\n\n        => Thus a sliding window is applicable here.\n\n        - Additionally, the dp array will consists of spans of equal numbers, e.g. 1112222223444...\n        => So we can just keep track when l move to a new span, no need to store the whole dp array.\n        """\n\n        h = 0\n        l = 0\n        span_start = 0\n        ans = 1\n        for r in range(n):\n            # expand the window one step to the right\n            h = (h * p + (ord(target[r]) - 96)) % M\n\n            # shrink the window from the left until found a valid prefix\n            while l <= r and h not in prefixes:\n                x = ord(target[l]) - 96\n                h = (h - (x * power[r - l])) % M\n                l += 1\n\n            # early stop if no valid prefix found\n            if l > r:\n                return -1\n\n            # when l moves to a new span is also when r starts the next span\n            if l > span_start:\n                ans += 1\n                span_start = r\n        \n        return ans\n```\n\n*This problem helped me reach Guardian after 2 years of practicing.*
['Dynamic Programming', 'Greedy', 'Trie', 'Sliding Window', 'Rolling Hash', 'Python3']