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:

1
2
3
4
5

Input:
s = "1000", k = 10000
Output:
 1
Explanation: The only possible array is [1000]

Example 2:

1
2
3
4
5

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:

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)), where n is the length of s and k is the upper bound for numbers. Each state tries up to log10(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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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)), where n is the length of s and k is the upper bound for numbers. Each state tries up to log10(k) splits.
  • 🧺 Space complexity: O(n), for the DP array.