<p>You wrote down many <strong>positive</strong> integers in a string called <code>num</code>. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was <strong>non-decreasing</strong> and that <strong>no</strong> integer had leading zeros.</p>

<p>Return <em>the <strong>number of possible lists of integers</strong> that you could have written down to get the string </em><code>num</code>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;327&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You could have written down the numbers:
3, 27
327
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;094&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> No numbers can have leading zeros and all numbers must be positive.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;0&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> No numbers can have leading zeros and all numbers must be positive.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 3500</code></li>
	<li><code>num</code> consists of digits <code>&#39;0&#39;</code> through <code>&#39;9&#39;</code>.</li>
</ul>

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        N = len(num)
        BIG = 10**9 + 7

        #### top-down, too slow but it's a start

        # def countWays(i: int, threshold: str) -> int:
        #     if i == N: return 1 # 1 way to parse empty sequence N:
            
        #     if i + len(threshold) > N: return 0 # not enough digits

        #     if num[i] == '0': return 0 # no leading zeros and must be positive

        #     ways = 0
        #     # for parsing len(threshold) digits from i, the corresponding number
        #     # might be lower than the prior digits
        #     L = len(threshold)
        #     if num[i:i+L] >= threshold:
        #         # take i:i+L and continue
        #         ways += countWays(i+L, num[i:i+L])

        #     # any longer number will work too
        #     for L2 in range(L+1, N-i+1):
        #         # take next L2 digits and continue, each is a different threshold later on
        #         ways += countWays(i+L2, num[i:i+L2])
        #         ways %= BIG

        #     return ways

        # # for i=0 it's a special case where there's no threshold
        # return countWays(0, '0')

        ### The above works, but it's O(N**3) time
        #  > we have O(N**2) states to fill in
        #  > and each requires O(N) for a string comparison
        #  > and each also requires a sum over O(N) other states

        # DP: each threshold is a substring i..j
        # and the prior substring ends with the current index i
        # so the call is really countWays(i, p) where p < i, p === "prior index"
        #     i==0 is a special case where there's no such p, there's no prior number
        #          so we'll have to handle that specially later

        # Now we need a recurrence relation
        #    ways[i][p] =
        #          1 if i == N,       parsing the empty string, 1 way
        #          0 if num[i] == 0,  no leading zeros
        #          0 if i+p > N,      not enough digits
        #
        # ways[i][p] =      start at i, all numbers must be at least num[p:i]
        #      parse i-p digits iff that number is at least num[p:i]: ways[i+i-p][i]
        #      parse i-p+1 digits: ways[i+i-p+1][i]
        #
        #
        # so ways[i][p] depends on ways[i' > i][i]
        # e.g. ways[3][1] is ways[5][3] if num[3:5] >= num[1:3] else 0
        #                    ways[6][3]
        #                    ways[7][3]
        #                    ...
        #                    ways[N][3]
        #
        # what other values reuse most of that sum?
        # things with the same i, but different p
        # ways[3][2] is ways[4][3] if num...
        #               ways[5][3]
        #               ways[6][3]
        #               ...

        # so i,p+1 uses the i,p sum, except
        #    > we add i+i-p,i no matter what, because p+1:i is shorter so it always counts
        #    > we also add i+i-(p+1), i, shorter prefix allows for 1 fewer digit to be parsed

        # finally we need to accelerate is num[i:i+i-p] >= num[p:i]
        #    > we need to know if the i-p digits at i are >= the prior i-p digits
        #    > which we can answer if we know the longest common prefix in O(1)

        if num[0] == '0': return 0

        lcp = [[0]*(N+1) for _ in range(N+1)]
        for i in range(N-1, -1, -1):
            for j in range(N-1, -1, -1):
                if num[i] == num[j]:
                    lcp[i][j] = 1 + lcp[i+1][j+1]

        # and so now we implement, i needs i' > i so we fill in reverse order
        ways = [[0]*N for _ in range(N)]
        ways.append([1]*N) # ways[N][p] == 1 for all p
        for i in range(N-1, 0, -1): # i==0 is a special case; no prefix
            if num[i] == '0': continue

            # from above, each ways[i][p] reuses most of ways[i][p' < p]
            #    there's the sum of ways to parse longer numbers, i.e. i' > i+i-p
            #    and maybe the way to parse i-p digits too
            #
            # the max p is i-1 b/c we parse at least one digit
            # the min p is 0
            #    FIXED: not really, because if we parsed p:i before then we
            #           need to parse at least i-p digits for the next number
            #           if i+i-p > N though this is impossible
            #           therefore we need 2*i-p <= N, i.e. p >= 2*i-N
            #           p >= 0 also must hold
            #
            # suppose the first p is p*
            # then longer_ways starts with ways to parse more than i-p* digits,
            # aka we can parse i-p*+1, i-p*+2, etc.
            #  which is ways[2*i-p*+1][i], ways[2*i-p*+2][i], .. ways[N][i]
            min_p = max(0, 2*i-N)
            longer_ways = sum(ways[j][i] for j in range(i+i-min_p+1, N+1))
            for p in range(max(2*i-N, 0), i):
                ways[i][p] = longer_ways # ways to parse more than i-p digits from here
                
                l = lcp[i][p]
                if l >= i-p or num[i+l] > num[p+l]: # O(1) form of num[i:i+i-p] >= num[p:i]
                    # i:i+(i-p) >= p:i so we can parse an i-p digit number here
                    ways[i][p] += ways[i+i-p][i]
                    ways[i][p] %= BIG

                # for next p, aka one fewer digit we parsed before i,
                # we can parse i-p digits for sure b/c it will be one more digit
                # (see above)
                longer_ways += ways[i+i-p][i]
                longer_ways %= BIG

        # Final pass: from top-down version, starting at index i=0 we can parse
        # any number of digits:
        #   1: ways[1][0]
        #   2: ways[2][0]
        #   etc.

        return sum(ways[i][0] for i in range(1, N+1)) % BIG
2381