Restore The Array: String Partition DP

You are given a digit string s and an integer k. A program was supposed to print an array of integers, where each integer is between 1 and k. But it forgot to print the spaces, so the array came out as the single string s. Your job is to figure out how many possible arrays could have produced this string. Since the answer can be huge, return it modulo 10^9 + 7.

This is LeetCode 1416: Restore The Array, and it is one of the cleanest examples of the string partition DP pattern. If you have worked through Decode Ways, the structure will feel very similar. The difference is that instead of mapping digits to letters (1-26), you are mapping substrings to arbitrary numbers between 1 and k, and k can be up to 10^9.

Why this problem matters

Restore The Array teaches you the general string partition DP pattern. In Decode Ways, the valid numbers are limited to 1-26, so you only ever look back 1 or 2 positions. Here, k can be billions, which means the lookback window scales with the number of digits in k. That forces you to think about how far back you need to search at each position, and the answer is at most log10(k) digits.

This same partition structure appears whenever you need to count the number of ways to split a string into valid segments:

• Restore The Array (this problem): segments are numbers between 1 and k
• Decode Ways (LeetCode 91): segments are numbers between 1 and 26
• Word Break (LeetCode 139): segments are dictionary words
• Palindrome Partitioning II (LeetCode 132): segments are palindromes

Once you internalize the string partition DP template, all of these become variations on the same idea.

The key insight

Define dp[i] as the number of ways to split the first i characters of s into valid numbers. For each position i, look back at all positions j where the substring s[j..i-1] forms a valid number. A number is valid if it has no leading zeros and its value is between 1 and k. For each valid j, add dp[j] to dp[i].

The recurrence is:

dp[i] = sum of dp[j] for all j where s[j..i-1] is a valid number (1 to k, no leading zeros)

The base case is dp[0] = 1, representing one way to split the empty prefix.

The key efficiency insight is that you do not need to check all j from 0 to i-1. Since k has at most len(str(k)) digits, you only need to look back that many positions. If the substring grows longer than k in digit count, it will always exceed k in value (or it would have been caught by leading-zero detection). This limits the inner loop to O(log k) iterations per position.

The solution

def numberOfArrays(s, k):
    MOD = 10**9 + 7
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    max_len = len(str(k))

    for i in range(1, n + 1):
        for length in range(1, max_len + 1):
            if length > i:
                break
            start = i - length
            substring = s[start:i]
            if substring[0] == '0':
                continue
            if int(substring) > k:
                break
            dp[i] = (dp[i] + dp[start]) % MOD

    return dp[n]

The outer loop walks through each position i from 1 to n. The inner loop tries every possible last-segment length, from 1 digit up to max_len digits (the number of digits in k). For each candidate substring, we check two things: does it start with a leading zero (skip it if so), and is its numeric value greater than k (stop looking at longer substrings if so). If the substring passes both checks, we add dp[start] to dp[i].

The break when int(substring) > k works because longer substrings will only be larger. If a 4-digit substring already exceeds k, no 5-digit substring starting earlier can be valid either.

Visual walkthrough

Let's trace through s = "1317" with k = 2000. At each position, we look back at all substrings that form valid numbers between 1 and 2000.

At each step, the number of valid splits grows because more substrings pass the validity check. The final answer dp[4] = 8 counts every way to partition "1317" into numbers between 1 and 2000.

Complexity analysis

The outer loop runs n times. The inner loop runs at most log10(k) times per position, since that is the maximum number of digits any valid number can have. The string comparison inside the inner loop is also bounded by log10(k). Space is O(n) for the dp array.

The building blocks

1. String partition DP template

The core template for string partition DP is:

dp[0] = 1
for i in range(1, n + 1):
    for each valid segment ending at position i:
        dp[i] += dp[start of that segment]

This template applies to any problem where you count the number of ways to split a string into valid parts. The only thing that changes is how you define and check validity. In this problem, a segment is valid if it represents a number between 1 and k with no leading zeros. In Word Break, a segment is valid if it appears in a dictionary. The DP skeleton is identical.

2. Substring number validation

Validating whether a substring represents a number between 1 and k requires two checks:

1. No leading zeros: if the first character is '0', the substring is invalid. Numbers like "07" or "00" are not valid representations.
2. Value within range: convert the substring to an integer and check that it is <= k. Since k can be up to 10^9, the substring can be up to 10 digits long.

The leading-zero check is critical. Without it, strings like "1000" would incorrectly count splits where a segment starts with zero. The problem statement says numbers are between 1 and k, which rules out zero itself and any number with leading zeros.

Edge cases

• String starts with '0': no valid array can start with a number that has a leading zero. dp[1] will be 0, and since all later dp values depend on earlier ones, the answer will be 0.
• All zeros like "0000": every position has a leading zero, so dp[i] = 0 for all i > 0. Answer: 0.
• Single digit "5" with k >= 5: one valid array [5]. Answer: 1.
• Single digit "5" with k = 3: the number 5 exceeds k, so no valid array exists. Answer: 0.
• Very large k: when k is 10^9, the inner loop checks up to 10 digits back. This is still efficient since 10 is a small constant.
• Very long string with small k: when k = 1, every digit must be '1'. If any digit is not '1', the answer is 0. If all digits are '1', the answer is 1.
• String with internal zeros like "1023": the '0' cannot start a segment. It must be part of a multi-digit number like "10" or "102". The leading-zero check handles this automatically.

From understanding to recall

You now understand how string partition DP works for this problem, and the recurrence probably makes sense. But will you remember the leading-zero check two weeks from now? Will you recall that the inner loop length is bounded by len(str(k))? Will you get the modular arithmetic right on the first try?

Understanding and recall are different skills. The string partition DP template is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling it with spaced repetition means you practice writing the solution from scratch at increasing intervals. After a few reps, the validity check, the base case, and the mod operation all become automatic.

Related posts

• Decode Ways - The classic string partition DP problem with a fixed range of 1-26, and the closest relative to Restore The Array
• Word Break - Same partition DP skeleton, but the validity check uses a dictionary lookup instead of a numeric range
• Palindrome Partitioning - Partition DP where each segment must be a palindrome, combining the partition template with palindrome checking