# Restore The Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/restore-the-array)
Canonical: https://scaleengineer.com/dsa/problems/restore-the-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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 <= 105`
* `s` consists of only digits and does not contain leading zeros.
* `1 <= k <= 109`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's partitioning nature into a recursive structure. We define a function that explores all possible ways to split the string from a given starting position. For each position, we try to form a valid number by taking one or more digits. If a valid number is formed, we recursively call the function for the rest of the string. The total number of ways is the sum of ways from all valid splits.
**Time:** Exponential, roughly O(2^N) in the worst case. The function `solve(i)` can call `solve(i+1), solve(i+2), ...`, leading to a large number of overlapping subproblems. · **Space:** O(N), where N is the length of the string `s`. This is for the recursion call stack depth.
**Pros:** Simple to conceptualize and implement based on the problem definition.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for larger inputs.
### Explanation
The core idea is to define a function `solve(i)` which computes the number of ways to decode the suffix of the string `s` starting at index `i`. The final answer is `solve(0)`.

To compute `solve(i)`, we can try to form the first number of the partition. This number can be `s[i]`, `s[i...i+1]`, `s[i...i+2]`, and so on. For each potential first number, say formed by `s[i...j]`, we check if it's valid. A number is valid if it's within the range `[1, k]` and doesn't have a leading zero. Since the problem statement guarantees `s` itself doesn't start with '0', we only need to check for leading zeros in subsequent partitions (i.e., if `s[i]` is '0'). If `s[i]` is '0', no valid partition can start from `i`, so `solve(i)` is 0.

If the number from `s[i...j]` is valid, we've found one valid way to form the first number. The remaining problem is to find how many ways the rest of the string, `s[j+1:]`, can be partitioned. This is exactly what `solve(j+1)` calculates. So, we add `solve(j+1)` to our total for `solve(i)`. We sum this over all valid `j`.

The base case for the recursion is when we have successfully parsed the entire string, i.e., when `i == s.length()`. This counts as one valid way, so we return 1.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private String s;
    private int k;

    public int numberOfArrays(String s, int k) {
        this.s = s;
        this.k = k;
        return solve(0);
    }

    private int solve(int index) {
        if (index == s.length()) {
            return 1; // Found a valid partition
        }
        if (s.charAt(index) == '0') {
            return 0; // Numbers cannot have leading zeros
        }

        long count = 0;
        long num = 0;
        for (int j = index; j < s.length(); j++) {
            num = num * 10 + (s.charAt(j) - '0');
            if (num > k) {
                break; // Number is too large, no need to check longer numbers
            }
            count = (count + solve(j + 1)) % MOD;
        }
        return (int) count;
    }
}
```
### Algorithm
1. Define a recursive function, say `solve(index)`, that calculates the number of ways to parse the suffix of the string `s` starting from `index`.
2. **Base Case**: If `index` reaches the end of the string (`s.length()`), it means we have successfully found one valid partition. Return 1.
3. **Recursive Step**: For the current `index`:
    a. If `s.charAt(index)` is '0', no valid number can be formed. Return 0.
    b. Initialize a counter for the number of ways, `count = 0`.
    c. Iterate from `j = index` to `s.length() - 1` to form substrings `s[index...j]`.
    d. Convert the substring to a number. Let's call it `num`.
    e. If `num` is greater than `k`, any longer substring starting at `index` will also be greater than `k`. So, break the loop.
    f. If `1 <= num <= k`, we have found a valid number. This means we can make a partition here. The number of ways to partition the rest of the string `s[j+1:]` is given by `solve(j + 1)`. Add this to `count`.
    g. Remember to perform calculations modulo `10^9 + 7`.
4. Return the final `count`.
5. The initial call to the function will be `solve(0)`.

## Top-Down Dynamic Programming (Memoization)
The brute-force recursive solution is slow because it repeatedly solves the same subproblems. For example, `solve(5)` might be called when partitioning `s[0:]`, `s[1:]`, `s[2:]`, etc. We can significantly optimize this by storing the result of each subproblem `solve(i)` the first time it's computed and reusing the stored result for subsequent calls. This technique is called memoization, which is a form of top-down dynamic programming.
**Time:** O(N * log K). Each state `dp[i]` is computed once. The loop to compute `dp[i]` runs at most `d` times, where `d` is the number of digits in `k` (i.e., `d` is approximately `log10(K)`). Any number with more digits than `k` will be larger than `k`. · **Space:** O(N) for both the recursion stack and the memoization array.
**Pros:** Drastically improves time complexity, making it efficient enough to pass the given constraints.; Maintains the logical structure of the recursive solution, making it relatively easy to implement.
**Cons:** Uses O(N) extra space for the memoization table.; For very deep recursion (large N), it might lead to a StackOverflowError, although this is less common in modern systems for N=10^5.
### Explanation
We augment the recursive solution with a memoization table, typically an array `memo`, to store the results of `solve(i)`. The `memo` array is initialized with a sentinel value (like -1) to indicate that a subproblem has not yet been solved.

When `solve(i)` is called, it first checks `memo[i]`. If `memo[i]` is not the sentinel value, it means we've already computed the answer for the suffix `s[i:]`, so we can just return the stored value. Otherwise, we proceed with the computation as before. Once the result is computed, we store it in `memo[i]` before returning. This ensures that each distinct subproblem `solve(i)` is computed only once.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private String s;
    private int k;
    private int[] memo;

    public int numberOfArrays(String s, int k) {
        this.s = s;
        this.k = k;
        this.memo = new int[s.length()];
        java.util.Arrays.fill(memo, -1);
        return solve(0);
    }

    private int solve(int index) {
        if (index == s.length()) {
            return 1;
        }
        if (s.charAt(index) == '0') {
            return 0;
        }
        if (memo[index] != -1) {
            return memo[index];
        }

        long count = 0;
        long num = 0;
        for (int j = index; j < s.length(); j++) {
            num = num * 10 + (s.charAt(j) - '0');
            if (num > k) {
                break;
            }
            count = (count + solve(j + 1)) % MOD;
        }
        
        return memo[index] = (int) count;
    }
}
```
### Algorithm
1. Use the same recursive structure as the brute-force approach.
2. Create a memoization array, `memo`, of size `N` (where `N` is the length of `s`), to store the results of `solve(index)`. Initialize it with a value indicating that the state has not been computed (e.g., -1).
3. In the recursive function `solve(index)`:
    a. First, check if `memo[index]` already contains a computed result. If so, return it immediately.
    b. If not, compute the result as in the brute-force approach.
    c. Before returning the computed result, store it in `memo[index]` for future use.
4. The rest of the logic remains the same.

## Bottom-Up Dynamic Programming
This approach is the iterative, or bottom-up, version of the dynamic programming solution. It eliminates recursion, which can prevent stack overflow issues and sometimes offers a slight performance improvement due to the removal of function call overhead. We build the solution from the smallest subproblems to the largest. The subproblem `dp[i]` (number of ways to parse `s[i:]`) is solved using the results of already solved subproblems `dp[j]` where `j > i`.
**Time:** O(N * log K). The outer loop runs N times, and the inner loop runs at most `d = log10(K)` times. · **Space:** O(N) for the DP array.
**Pros:** Avoids recursion and potential stack overflow errors.; Often slightly more performant than memoization due to no recursion overhead.; Clear and systematic way to build the solution from base cases.
**Cons:** Uses O(N) space, which might be a concern for extremely large N, although it's acceptable for the given constraints.
### Explanation
We define a `dp` array where `dp[i]` holds the number of ways to restore the array from the suffix `s[i:]`. The size of this array will be `N+1`.

The base case is `dp[N] = 1`, as there's one way to parse an empty suffix (by doing nothing). We then iterate backward from `i = N-1` to `0`. For each `i`, we calculate `dp[i]` by considering all possible first numbers that can be formed starting at `s[i]`. 

For each `i`, we iterate `j` from `i` to `N-1`, forming a number from the substring `s[i...j]`. If this number is valid (i.e., `1 <= num <= k` and no leading zero), we can make a cut after `j`. The number of ways to parse the rest of the string `s[j+1:]` is already computed and stored in `dp[j+1]`. We add this to the total for `dp[i]`. We continue this process until the number formed exceeds `k` or we reach the end of the string.

```java
class Solution {
    public int numberOfArrays(String s, int k) {
        int n = s.length();
        int MOD = 1_000_000_007;
        int[] dp = new int[n + 1];
        dp[n] = 1; // Base case: one way to parse an empty string

        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
                continue;
            }

            long num = 0;
            long count = 0;
            for (int j = i; j < n; j++) {
                num = num * 10 + (s.charAt(j) - '0');
                if (num > k) {
                    break;
                }
                count = (count + dp[j + 1]) % MOD;
            }
            dp[i] = (int) count;
        }

        return dp[0];
    }
}
```
### Algorithm
1. Create a DP array, `dp`, of size `N+1`. `dp[i]` will store the number of ways to parse the suffix `s[i:]`.
2. **Base Case**: Initialize `dp[N] = 1`. This signifies that there is one way to parse an empty string (the empty partition).
3. **Iteration**: Loop `i` from `N-1` down to `0`.
    a. If `s.charAt(i)` is '0', set `dp[i] = 0` and continue to the next `i`.
    b. Otherwise, initialize `dp[i] = 0`.
    c. Start forming a number `num` from `s[i]`. Iterate with `j` from `i` to `N-1`.
    d. In each step of the inner loop, update `num` with the next digit `s.charAt(j)`.
    e. If `num` exceeds `k`, break the inner loop.
    f. If `num` is valid, add `dp[j+1]` to `dp[i]`. `dp[j+1]` contains the pre-computed number of ways to parse the rest of the string.
    g. Perform additions modulo `10^9 + 7`.
4. **Result**: The final answer is `dp[0]`, which is the number of ways to parse the entire string `s[0:]`.

## Space-Optimized Bottom-Up DP
This approach optimizes the space complexity of the bottom-up DP solution. By analyzing the dependencies in the DP recurrence relation, `dp[i] = sum(dp[j+1])`, we notice that `dp[i]` only depends on states `dp[j+1]` where the length of the number `s[i...j]` is at most `d = log10(K)`. This means `j` is at most `i+d-1`, so `dp[i]` depends only on `dp[i+1]` through `dp[i+d]`. Instead of keeping the entire `O(N)` DP table, we only need to maintain a sliding window of `d+1` most recent values.
**Time:** O(N * log K). The time complexity is identical to the non-space-optimized DP approaches. · **Space:** O(log K). The size of the DP array is proportional to the number of digits in `k`.
**Pros:** Most efficient solution in terms of space complexity.; Maintains the optimal time complexity.
**Cons:** The implementation is slightly more complex due to managing indices in the circular array.
### Explanation
The time complexity of the bottom-up DP is efficient, but the `O(N)` space can be improved. The calculation of `dp[i]` requires values `dp[i+1], dp[i+2], ...` up to `dp[i+d]`, where `d` is the number of digits in `k`. We don't need `dp[i+d+1]` or any subsequent values. This suggests we can use a space-optimized DP table of size `d+1` that acts as a circular array.

We can use the modulo operator to map an index `i` from the original `O(N)` DP table to an index in our `O(d)` table. For example, `dp[i]` is stored at `dp_opt[i % (d+1)]`. The logic for calculating the DP value at each step remains identical to the standard bottom-up approach, but all accesses to the DP table are mapped through the modulo operator. This reduces the space complexity from `O(N)` to `O(d)`, which is `O(log K)`. Since `k <= 10^9`, `d` is at most 10, making the space usage constant and very small.

```java
class Solution {
    public int numberOfArrays(String s, int k) {
        int n = s.length();
        int MOD = 1_000_000_007;
        int d = String.valueOf(k).length();
        
        // dp_opt will store the last d+1 values of our DP table.
        int[] dp_opt = new int[d + 1];
        dp_opt[n % (d + 1)] = 1; // Base case

        for (int i = n - 1; i >= 0; i--) {
            int i_mod = i % (d + 1);
            dp_opt[i_mod] = 0; // Reset for current calculation

            if (s.charAt(i) == '0') {
                continue;
            }

            long num = 0;
            long count = 0;
            for (int j = i; j < n; j++) {
                // Optimization: a number with more digits than k is always larger.
                if (j - i + 1 > d) {
                    break;
                }
                num = num * 10 + (s.charAt(j) - '0');
                if (num > k) {
                    break;
                }
                int j_mod = (j + 1) % (d + 1);
                count = (count + dp_opt[j_mod]) % MOD;
            }
            dp_opt[i_mod] = (int) count;
        }

        return dp_opt[0];
    }
}
```
### Algorithm
1. Let `d` be the number of digits in `k`. Any valid number formed from `s` cannot have more than `d` digits.
2. We observe that `dp[i]` depends only on `dp[i+1], dp[i+2], ..., dp[i+d]`. This means we only need to store the last `d+1` values of the DP table at any time.
3. Create a smaller DP array, `dp_opt`, of size `d+1`.
4. We will use this array as a circular buffer. `dp_opt[i % (d+1)]` will store the value for `dp[i]`.
5. **Base Case**: Initialize `dp_opt[N % (d+1)] = 1`.
6. **Iteration**: Loop `i` from `N-1` down to `0`.
    a. Calculate the value for `dp[i]` using the same logic as the standard bottom-up DP.
    b. When you need `dp[j+1]`, access it from the circular array as `dp_opt[(j+1) % (d+1)]`.
    c. Store the final computed value for `dp[i]` in `dp_opt[i % (d+1)]`.
7. **Result**: The final answer is `dp_opt[0 % (d+1)]`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfArrays(String s, int k) {
    final int MODULO = 1000000007;
    int length = s.length();
    int kLength = String.valueOf(k).length();
    int[] dp = new int[length];
    dp[0] = 1;
    for (int i = 1; i < length; i++) {
      if (i < kLength && Long.parseLong(s.substring(0, i + 1)) <= (long)k)
        dp[i]++;
      int min = Math.max(0, i - kLength);
      for (int j = min; j < i; j++) {
        if (s.charAt(j + 1) == '0')
          continue;
        long curNum = Long.parseLong(s.substring(j + 1, i + 1));
        if (curNum <= (long)k)
          dp[i] = (dp[i] + dp[j]) % MODULO;
      }
    }
    return dp[length - 1];
  }
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/restore-the-array/ // Time: O(N^2) // Space: O(N) class Solution { typedef long long LL ; public: int numberOfArrays ( string s , int k ) { if ( s [ 0 ] - '0' > k ) return 0 ; int cnt = 0 , tmp = k ; while ( tmp ) { tmp /= 10 ; ++ cnt ; } int N = s . size (), mod = 1e9 + 7 ; vector < int > dp ( N + 1 ); dp [ 0 ] = dp [ 1 ] = 1 ; for ( int i = 2 ; i <= N ; ++ i ) { LL p = 1 , n = 0 ; for ( int j = i - 1 ; j >= 0 ; -- j ) { n += ( s [ j ] - '0' ) * p ; p *= 10 ; if ( n > k || i - j > cnt ) break ; if ( n == 0 || s [ j ] == '0' ) continue ; dp [ i ] = ( dp [ i ] + dp [ j ]) % mod ; } } return dp [ N ]; } };
```