Watch 10 video solutions for Restore The Array, a hard level problem involving String, Dynamic Programming. This walkthrough by codestorywithMIK has 7,358 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |