Restore The Array
HardUpdated: Aug 2, 2025
Practice on:
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 10^9 + 7.
Examples
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]
Solution
Method 1 - DP with Memo
Intuition
Use recursion and memoization to count the number of ways to split the string into valid numbers in [1, k] with no leading zeros. At each position, try all possible splits and sum the results.
Approach
Define a recursive function with memoization that, for each index, tries all possible substrings starting at that index that form valid numbers. For each valid split, recursively count the ways for the remaining substring.
Code
C++
class Solution {
public:
int numberOfArrays(string s, int k) {
const int MOD = 1e9 + 7;
int n = s.size();
vector<int> dp(n, -1);
function<int(int)> dfs = [&](int i) {
if (i == n) return 1;
if (s[i] == '0') return 0;
if (dp[i] != -1) return dp[i];
int ans = 0;
long num = 0;
for (int j = i; j < n; ++j) {
num = num * 10 + (s[j] - '0');
if (num > k) break;
ans = (ans + dfs(j + 1)) % MOD;
}
return dp[i] = ans;
};
return dfs(0);
}
};
Go
func numberOfArrays(s string, k int) int {
const MOD = 1_000_000_007
n := len(s)
dp := make([]int, n)
for i := range dp {
dp[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i == n {
return 1
}
if s[i] == '0' {
return 0
}
if dp[i] != -1 {
return dp[i]
}
ans := 0
num := 0
for j := i; j < n; j++ {
num = num*10 + int(s[j]-'0')
if num > k {
break
}
ans = (ans + dfs(j+1)) % MOD
}
dp[i] = ans
return ans
}
return dfs(0)
}
Java
class Solution {
public int numberOfArrays(String s, int k) {
final int MOD = 1_000_000_007;
int n = s.length();
Integer[] dp = new Integer[n];
return dfs(s, k, 0, dp, MOD);
}
private int dfs(String s, long k, int i, Integer[] dp, int MOD) {
if (i == s.length()) return 1;
if (s.charAt(i) == '0') return 0;
if (dp[i] != null) return dp[i];
int ans = 0;
long num = 0;
for (int j = i; j < s.length(); j++) {
num = num * 10 + s.charAt(j) - '0';
if (num > k) break;
ans = (ans + dfs(s, k, j + 1, dp, MOD)) % MOD;
}
return dp[i] = ans;
}
}
Kotlin
class Solution {
fun numberOfArrays(s: String, k: Int): Int {
val MOD = 1_000_000_007
val n = s.length
val dp = Array<Int?>(n) { null }
fun dfs(i: Int): Int {
if (i == n) return 1
if (s[i] == '0') return 0
dp[i]?.let { return it }
var ans = 0
var num = 0L
for (j in i until n) {
num = num * 10 + (s[j] - '0')
if (num > k) break
ans = (ans + dfs(j + 1)) % MOD
}
dp[i] = ans
return ans
}
return dfs(0)
}
}
Python
class Solution:
def numberOfArrays(self, s: str, k: int) -> int:
MOD = 10**9 + 7
n = len(s)
dp = [-1] * n
def dfs(i):
if i == n:
return 1
if s[i] == '0':
return 0
if dp[i] != -1:
return dp[i]
ans = 0
num = 0
for j in range(i, n):
num = num * 10 + int(s[j])
if num > k:
break
ans = (ans + dfs(j + 1)) % MOD
dp[i] = ans
return ans
return dfs(0)
Rust
impl Solution {
pub fn number_of_arrays(s: String, k: i32) -> i32 {
const MOD: i32 = 1_000_000_007;
let n = s.len();
let s = s.as_bytes();
let mut dp = vec![-1; n];
fn dfs(i: usize, s: &[u8], k: i32, dp: &mut Vec<i32>) -> i32 {
if i == s.len() { return 1; }
if s[i] == b'0' { return 0; }
if dp[i] != -1 { return dp[i]; }
let mut ans = 0;
let mut num = 0i64;
for j in i..s.len() {
num = num * 10 + (s[j] - b'0') as i64;
if num > k as i64 { break; }
ans = (ans + dfs(j + 1, s, k, dp)) % MOD as i64;
}
dp[i] = ans as i32;
ans as i32
}
dfs(0, &s, k, &mut dp)
}
}
TypeScript
function numberOfArrays(s: string, k: number): number {
const MOD = 1_000_000_007;
const n = s.length;
const dp: number[] = Array(n).fill(-1);
function dfs(i: number): number {
if (i === n) return 1;
if (s[i] === '0') return 0;
if (dp[i] !== -1) return dp[i];
let ans = 0;
let num = 0;
for (let j = i; j < n; j++) {
num = num * 10 + Number(s[j]);
if (num > k) break;
ans = (ans + dfs(j + 1)) % MOD;
}
dp[i] = ans;
return ans;
}
return dfs(0);
}
Complexity
- ⏰ Time complexity:
O(n * log10(k)), wherenis the length ofsandkis the upper bound for numbers. Each state tries up tolog10(k)splits. - 🧺 Space complexity:
O(n), for the memoization table.
Method 2 -
Method 2 - Bottom Up DP
Intuition
Instead of recursion, use a DP array where dp[i] is the number of ways to split the substring s[i:] into valid numbers. Fill the array from the end to the start.
Approach
Iterate backwards through the string. For each position, try all valid splits (numbers in [1, k] with no leading zeros) and sum the ways from the next position. Use modulo for large results.
Code
C++
class Solution {
public:
int numberOfArrays(string s, int k) {
const int MOD = 1e9 + 7;
int n = s.size();
vector<int> dp(n + 1);
dp[n] = 1;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '0') continue;
long num = 0;
for (int j = i; j < n; ++j) {
num = num * 10 + (s[j] - '0');
if (num > k) break;
dp[i] = (dp[i] + dp[j + 1]) % MOD;
}
}
return dp[0];
}
};
Go
func numberOfArrays(s string, k int) int {
const MOD = 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
}
num := 0
for j := i; j < n; j++ {
num = num*10 + int(s[j]-'0')
if num > k {
break
}
dp[i] = (dp[i] + dp[j+1]) % MOD
}
}
return dp[0]
}
Java
class Solution {
public int numberOfArrays(String s, int k) {
final int MOD = 1_000_000_007;
int n = s.length();
int[] dp = new int[n + 1];
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == '0') continue;
long num = 0;
for (int j = i; j < n; j++) {
num = num * 10 + s.charAt(j) - '0';
if (num > k) break;
dp[i] = (int)((dp[i] + dp[j + 1]) % MOD);
}
}
return dp[0];
}
}
Kotlin
class Solution {
fun numberOfArrays(s: String, k: Int): Int {
val MOD = 1_000_000_007
val n = s.length
val dp = IntArray(n + 1)
dp[n] = 1
for (i in n - 1 downTo 0) {
if (s[i] == '0') continue
var num = 0L
for (j in i until n) {
num = num * 10 + (s[j] - '0')
if (num > k) break
dp[i] = (dp[i] + dp[j + 1]) % MOD
}
}
return dp[0]
}
}
Python
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
num = 0
for j in range(i, n):
num = num * 10 + int(s[j])
if num > k:
break
dp[i] = (dp[i] + dp[j + 1]) % MOD
return dp[0]
Rust
impl Solution {
pub fn number_of_arrays(s: String, k: i32) -> i32 {
const MOD: i32 = 1_000_000_007;
let n = s.len();
let s = s.as_bytes();
let mut dp = vec![0; n + 1];
dp[n] = 1;
for i in (0..n).rev() {
if s[i] == b'0' { continue; }
let mut num = 0i64;
for j in i..n {
num = num * 10 + (s[j] - b'0') as i64;
if num > k as i64 { break; }
dp[i] = (dp[i] + dp[j + 1]) % MOD;
}
}
dp[0]
}
}
TypeScript
function numberOfArrays(s: string, k: number): number {
const MOD = 1_000_000_007;
const n = s.length;
const dp: number[] = Array(n + 1).fill(0);
dp[n] = 1;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === '0') continue;
let num = 0;
for (let j = i; j < n; j++) {
num = num * 10 + Number(s[j]);
if (num > k) break;
dp[i] = (dp[i] + dp[j + 1]) % MOD;
}
}
return dp[0];
}
Complexity
- ⏰ Time complexity:
O(n * log10(k)), wherenis the length ofsandkis the upper bound for numbers. Each state tries up tolog10(k)splits. - 🧺 Space complexity:
O(n), for the DP array.