LeetCode 1416 - Restore The Array

LeetCode Problem 1416

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem gives us a string s that represents several positive integers concatenated together without spaces. Originally, the array contained integers in the range [1, k], and none of the integers had leading zeros.

Our task is to determine how many different valid arrays could have produced the string s.

For example, if:

s = "1317"
k = 2000

then several valid splits are possible:

[1317]
[131,7]
[13,17]
[1,317]
[13,1,7]
[1,31,7]
[1,3,17]
[1,3,1,7]

The answer is therefore 8.

The key challenge is deciding where to split the string. Every substring must satisfy two conditions:

1. It must not contain leading zeros.
2. Its numeric value must be between 1 and k.

The constraints are extremely important:

• s.length can be as large as 10^5
• k can be up to 10^9

A brute-force solution that tries all possible splits would be exponentially slow because every position could potentially either split or not split.

The input guarantees that s itself does not begin with a leading zero, but substrings formed during splitting may still start with '0', and those substrings are invalid.

Several edge cases are important:

• Strings containing zeros in difficult positions, such as "1000"
• Very small k, which invalidates many substrings
• Large inputs where recursion without memoization would time out
• Cases where no valid split exists
• Cases where every digit can be split independently

Because the answer can become extremely large, we must return it modulo:

10^9 + 7

Approaches

Brute Force Approach

The brute-force strategy is to recursively try every possible split.

At each index, we consider all substrings starting from that position:

s[i:j]

If the substring is valid, meaning:

• it does not start with '0'
• its integer value is at most k

then we recursively solve the remaining suffix.

This approach is correct because it explores every possible partition of the string.

However, it is far too slow. In the worst case, every position can branch into multiple recursive calls, leading to exponential complexity. With 10^5 characters, this becomes completely infeasible.

Key Insight

The problem has overlapping subproblems.

If we define:

dp[i] = number of ways to restore the substring s[i:]

then many recursive paths repeatedly compute the same suffix results.

This naturally suggests dynamic programming.

At each index i, we try extending the current number digit by digit until:

• the number exceeds k
• or we reach the end of the string

For every valid number formed, we add:

dp[next_position]

to the answer.

Because k <= 10^9, any valid number can contain at most 10 digits. This is extremely important because it limits the amount of work performed at each position.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every possible split recursively
Optimal Dynamic Programming	O(n * log10(k))	O(n)	Reuses overlapping subproblems efficiently

Algorithm Walkthrough

1. Create a DP array where dp[i] represents the number of valid ways to restore the substring starting at index i.
2. Initialize the base case:

dp[n] = 1

where n is the length of the string.

This means there is exactly one way to restore an empty suffix, by choosing nothing. 3. Process the string from right to left.

We move backward because each state depends on future states. 4. At each index i, first check whether:

s[i] == '0'

If so, no valid number can start here because leading zeros are forbidden.

Therefore:

dp[i] = 0

5. Otherwise, begin constructing numbers digit by digit.

Start with:

current_number = 0

Then extend the substring one character at a time. 6. For every extension:

current_number = current_number * 10 + digit

7. If current_number > k, stop immediately.

Any longer substring will only become larger. 8. Otherwise, add the number of ways from the next position:

dp[i] += dp[j + 1]

9. Apply modulo arithmetic after each addition.
10. After processing all indices, return:

dp[0]

Why it works

The algorithm works because every valid array restoration corresponds to choosing a valid first number and then restoring the remaining suffix independently.

For each index i, the DP state counts all valid decompositions of s[i:]. By trying every valid next number and summing the solutions of the remaining suffixes, we enumerate every legal partition exactly once.

The recurrence is:

$dp[i] = \sum dp[j+1]$

where each substring s[i:j] forms a valid integer in [1, k].

Python Solution

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)

        dp = [0] * (n + 1)
        dp[n] = 1

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue

            current_number = 0

            for j in range(i, n):
                current_number = current_number * 10 + int(s[j])

                if current_number > k:
                    break

                dp[i] = (dp[i] + dp[j + 1]) % MOD

        return dp[0]

The implementation directly follows the dynamic programming strategy described earlier.

The array dp stores the number of ways to restore each suffix. The base case dp[n] = 1 represents the empty suffix.

The outer loop iterates backward through the string because each position depends on future states.

When a digit '0' is encountered, the loop skips processing because numbers cannot begin with leading zeros.

The inner loop gradually constructs numbers by extending the substring one digit at a time. As soon as the number exceeds k, the loop stops because any further extension would only increase the value.

For every valid number, the algorithm adds the number of restoration ways from the next index.

Modulo arithmetic prevents integer overflow and satisfies the problem requirements.

Go Solution

func numberOfArrays(s string, k int) int {
	const MOD int = 1_000_000_007

	n := len(s)

	dp := make([]int, n+1)
	dp[n] = 1

	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			continue
		}

		currentNumber := 0

		for j := i; j < n; j++ {
			currentNumber = currentNumber*10 + int(s[j]-'0')

			if currentNumber > k {
				break
			}

			dp[i] = (dp[i] + dp[j+1]) % MOD
		}
	}

	return dp[0]
}

The Go implementation mirrors the Python logic closely.

Because Go does not have Python's arbitrary precision integers by default, we rely on the fact that k <= 10^9, so int is sufficient.

Character-to-digit conversion is performed using:

int(s[j] - '0')

The DP slice is initialized with size n + 1, and the base case dp[n] = 1 is identical to the Python solution.

Worked Examples

Example 1

s = "1000"
k = 10000

We compute DP from right to left.

Index	Substring	Valid Choices	dp Value
4	""	base case	1
3	"0"	none	0
2	"00"	none	0
1	"000"	none	0
0	"1000"	1000	1

Detailed processing at index 0:

Substring	Value	Valid?	Added
"1"	1	yes	dp[1] = 0
"10"	10	yes	dp[2] = 0
"100"	100	yes	dp[3] = 0
"1000"	1000	yes	dp[4] = 1

Final answer:

dp[0] = 1

Example 2

s = "1000"
k = 10

Valid numbers cannot exceed 10.

At index 0:

Substring	Value	Valid?
"1"	1	yes
"10"	10	yes
"100"	100	no

But both "1" and "10" lead to suffixes beginning with '0', which are invalid.

Therefore:

dp[0] = 0

Example 3

s = "1317"
k = 2000

DP table construction:

Index	Possible Numbers	Contributions	dp[i]
4	base case	1	1
3	7	dp[4]	1
2	1, 17	dp[3] + dp[4]	2
1	3, 31, 317	dp[2] + dp[3] + dp[4]	4
0	1, 13, 131, 1317	dp[1] + dp[2] + dp[3] + dp[4]	8

Final answer:

8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log10(k))	Each index explores at most the digit length of k
Space	O(n)	DP array stores one value per position

The important optimization is that we never examine arbitrarily long substrings.

Since k <= 10^9, a valid number can contain at most 10 digits. Therefore, each index performs only a small constant amount of work, making the overall runtime effectively linear in the size of the string.

Test Cases

sol = Solution()

assert sol.numberOfArrays("1000", 10000) == 1  # single valid number
assert sol.numberOfArrays("1000", 10) == 0  # impossible because of zeros
assert sol.numberOfArrays("1317", 2000) == 8  # provided example

assert sol.numberOfArrays("1", 1) == 1  # smallest valid input
assert sol.numberOfArrays("9", 8) == 0  # single digit exceeds k
assert sol.numberOfArrays("123", 1000) == 4  # many valid partitions
assert sol.numberOfArrays("123", 12) == 2  # restricted by k
assert sol.numberOfArrays("111111", 111111) > 0  # many overlapping states
assert sol.numberOfArrays("101", 1000) == 1  # only [101] works
assert sol.numberOfArrays("101", 10) == 1  # [10,1]
assert sol.numberOfArrays("1001", 10000) == 1  # only full number valid
assert sol.numberOfArrays("1001", 10) == 0  # impossible split
assert sol.numberOfArrays("9999999999", 1000000000) >= 0  # large values
assert sol.numberOfArrays("123456789", 9) == 1  # only single digits allowed

Test Case Summary

Test	Why
"1000", 10000	Valid full-number restoration
"1000", 10	No valid partition exists
"1317", 2000	Multiple valid decompositions
"1", 1	Minimum input size
"9", 8	Single number exceeds limit
"123", 1000	Many valid splits
"123", 12	Restrictive k blocks longer substrings
"111111", 111111	Heavy overlapping subproblems
"101", 1000	Internal zero handling
"101", 10	Mixed valid and invalid partitions
"1001", 10000	Entire string must remain intact
"1001", 10	Leading zero issues invalidate splits
"9999999999", 1000000000	Large numeric values
"123456789", 9	Only single-digit partitions valid

Edge Cases

One important edge case involves substrings beginning with '0'. Since leading zeros are forbidden, any partition that starts with zero must immediately be rejected. A common bug is accidentally allowing substrings like "01" or "000". The implementation handles this by skipping processing whenever s[i] == '0'.

Another critical edge case occurs when numbers exceed k. Once the current constructed number becomes larger than k, continuing to extend the substring is pointless because additional digits only increase the value further. The implementation immediately breaks out of the inner loop, which is both correct and efficient.

A third important edge case is when no valid restoration exists at all. For example:

s = "1000"
k = 10

Every possible split eventually produces a segment with leading zeros or a number larger than k. The DP naturally propagates zeros upward, resulting in a final answer of 0.

Large inputs are also significant. Since s.length can reach 10^5, recursive brute-force solutions without memoization would cause exponential runtime or stack overflow. The bottom-up DP approach avoids recursion entirely and runs efficiently even at maximum input size.