A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.
Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: s = "1000", k = 10000 Output: 1 Explanation: The only possible array is [1000]
Example 2:
Input: s = "1000", k = 10 Output: 0 Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.
Example 3:
Input: s = "1317", k = 2000 Output: 8 Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
Constraints:
1 <= s.length <= 105s consists of only digits and does not contain leading zeros.1 <= k <= 109Problem Overview: You are given a digit string s that originally represented an array of integers, but all spaces were removed. Each number in the original array must be in the range [1, k] and cannot contain leading zeros. The task is to count how many valid arrays could produce the given string.
Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(n * log k), Space: O(n))
Think of the string as a sequence of choices. Starting at index i, you try forming numbers by extending the substring s[i..j]. Stop when the number exceeds k or when you encounter a leading zero. For each valid number, recursively compute the number of ways to restore the remainder of the string starting at j + 1. Use memoization to cache results for each starting index so repeated states are not recomputed. Each index explores at most len(k) digits (maximum digits in k), making the total complexity linear relative to the string length. This is a classic recursion-to-DP transition using string parsing and dynamic programming.
Approach 2: Dynamic Programming with Substring Checking (Bottom-Up) (Time: O(n * log k), Space: O(n))
The bottom-up DP version eliminates recursion. Define dp[i] as the number of ways to restore the suffix starting at index i. Initialize dp[n] = 1 since an empty suffix has one valid reconstruction. Iterate backward through the string. For each index i, attempt to build numbers by extending the substring up to len(k) digits. Convert the growing substring to an integer and stop when it exceeds k. If the substring starts with '0', skip it immediately because leading zeros are invalid. Add dp[j + 1] to dp[i] for every valid split. This approach works because every valid prefix decision reduces the problem to a smaller suffix, a standard pattern in dynamic programming problems involving string segmentation.
Recommended for interviews: The bottom-up dynamic programming approach is typically preferred. It avoids recursion depth limits and clearly demonstrates state definition (dp[i]), transition logic, and pruning based on k. Starting with the recursive memoized version shows you understand the problem structure, while converting it to iterative DP demonstrates strong optimization and implementation skills.
This approach uses dynamic programming to solve the problem. The main idea is to keep a dp array where dp[i] represents the number of ways to partition the substring s[0...i] into valid numbers less than or equal to k.
We iterate over the string s, and for each position, we try to form numbers ending at that position by taking substrings of varying lengths. If a substring is valid, we update the dp array.
The Python solution defines a function numberOfArrays where a dynamic programming table dp is used to track the number of ways to partition the string up to each index. For each end index i, it checks up to the last 10 digits (as k is very large, we can have up to 10 digits) to ensure the number formed is valid (i.e., not starting with zero unless it's a single digit and <= k). The results are stored in the dp array and modulo operation is used to prevent overflow.
Time Complexity: O(n * min(n, log10(k)))
Space Complexity: O(n)
This approach uses recursion with memoization to explore all possible partitions of the string and calculate the number of ways to divide it into valid numbers. It memorizes the results of subproblems to avoid redundant calculations and improve efficiency.
The Java recursive solution with memoization begins by defining a recursive helper function that takes the current index and explores all paths for substring partitioning, caching results with a HashMap to avoid recomputation. The break occurs if a number exceeds k, ensuring efficiency.
Java
JavaScript
Time Complexity: O(n * log10(k))
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Dynamic Programming with Substring Checking | Time Complexity: O(n * min(n, log10(k))) |
| Recursive with Memoization | Time Complexity: O(n * log10(k)) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * log k) | O(n) | When reasoning about the problem recursively or explaining the DP transition in interviews |
| Dynamic Programming with Substring Checking (Bottom-Up) | O(n * log k) | O(n) | Preferred production and interview solution; avoids recursion and processes the string in a single DP pass |
Restore The Array - (GOOGLE, MICROSOFT) | Recur+Memo | Leetcode-1416 | Live Code + Explanation • codestorywithMIK • 7,358 views views
Watch 9 more video solutions →Practice Restore The Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor