Problem

You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was non-decreasing and that no integer had leading zeros.

Return _thenumber of possible lists of integers that you could have written down to get the string _num. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3
4
5

Input: num = "327"
Output: 2
Explanation: You could have written down the numbers:
3, 27
327

Example 2

1
2
3

Input: num = "094"
Output: 0
Explanation: No numbers can have leading zeros and all numbers must be positive.

Example 3

1
2
3

Input: num = "0"
Output: 0
Explanation: No numbers can have leading zeros and all numbers must be positive.

Constraints

  • 1 <= num.length <= 3500
  • num consists of digits '0' through '9'.

Solution

Method 1 – Dynamic Programming with Suffix Array (LCP)

Intuition

We want to split the string into non-decreasing positive integers with no leading zeros. For each position, we can try all possible previous splits and check if the new number is at least as large as the previous. To compare large numbers efficiently, we use precomputed LCP (longest common prefix) arrays.

Approach

  1. Precompute the LCP array for all pairs of positions in the string.
  2. Use DP: let dp[i] be the number of ways to split the prefix num[:i].
  3. For each end position i, try all possible start positions j < i, and if num[j:i] is valid and non-decreasing, add dp[j] to dp[i].
  4. Use the LCP array to compare num[j-k:j] and num[j:i] efficiently.
  5. Return dp[n].

Code

 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

class Solution {
public:
    int numberOfCombinations(string num) {
        int n = num.size(), mod = 1e9+7;
        if (num[0] == '0') return 0;
        vector<vector<int>> lcp(n+1, vector<int>(n+1));
        for (int i = n-1; i >= 0; --i)
            for (int j = n-1; j >= 0; --j)
                lcp[i][j] = (num[i] == num[j] ? lcp[i+1][j+1]+1 : 0);
        vector<vector<int>> dp(n+1, vector<int>(n+1));
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= i; ++k) {
                if (num[i-k] == '0') continue;
                if (i-k == 0) { dp[i][k] = 1; continue; }
                int j = i-k;
                if (j-k >= 0) {
                    int cmp = lcp[j-k][i-k];
                    if (cmp >= k || num[j-k+cmp] <= num[i-k+cmp])
                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod;
                }
                for (int t = 1; t < k && j-t >= 0; ++t)
                    dp[i][k] = (dp[i][k] + dp[j][t]) % mod;
            }
        }
        int ans = 0;
        for (int k = 1; k <= n; ++k) ans = (ans + dp[n][k]) % mod;
        return ans;
    }
};
 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
33
34

func numberOfCombinations(num string) int {
    n, mod := len(num), int(1e9+7)
    if num[0] == '0' { return 0 }
    lcp := make([][]int, n+1)
    for i := range lcp { lcp[i] = make([]int, n+1) }
    for i := n-1; i >= 0; i-- {
        for j := n-1; j >= 0; j-- {
            if num[i] == num[j] {
                lcp[i][j] = lcp[i+1][j+1] + 1
            }
        }
    }
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    for i := 1; i <= n; i++ {
        for k := 1; k <= i; k++ {
            if num[i-k] == '0' { continue }
            if i-k == 0 { dp[i][k] = 1; continue }
            j := i-k
            if j-k >= 0 {
                cmp := lcp[j-k][i-k]
                if cmp >= k || num[j-k+cmp] <= num[i-k+cmp] {
                    dp[i][k] = (dp[i][k] + dp[j][k]) % mod
                }
            }
            for t := 1; t < k && j-t >= 0; t++ {
                dp[i][k] = (dp[i][k] + dp[j][t]) % mod
            }
        }
    }
    ans := 0
    for k := 1; k <= n; k++ { ans = (ans + dp[n][k]) % mod }
    return ans
}
 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

class Solution {
    public int numberOfCombinations(String num) {
        int n = num.length(), mod = 1_000_000_007;
        if (num.charAt(0) == '0') return 0;
        int[][] lcp = new int[n+1][n+1];
        for (int i = n-1; i >= 0; i--)
            for (int j = n-1; j >= 0; j--)
                lcp[i][j] = (num.charAt(i) == num.charAt(j) ? lcp[i+1][j+1]+1 : 0);
        int[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= i; k++) {
                if (num.charAt(i-k) == '0') continue;
                if (i-k == 0) { dp[i][k] = 1; continue; }
                int j = i-k;
                if (j-k >= 0) {
                    int cmp = lcp[j-k][i-k];
                    if (cmp >= k || num.charAt(j-k+cmp) <= num.charAt(i-k+cmp))
                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod;
                }
                for (int t = 1; t < k && j-t >= 0; t++)
                    dp[i][k] = (dp[i][k] + dp[j][t]) % mod;
            }
        }
        int ans = 0;
        for (int k = 1; k <= n; k++) ans = (ans + dp[n][k]) % mod;
        return ans;
    }
}
 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

class Solution {
    fun numberOfCombinations(num: String): Int {
        val n = num.length
        val mod = 1_000_000_007
        if (num[0] == '0') return 0
        val lcp = Array(n+1) { IntArray(n+1) }
        for (i in n-1 downTo 0) for (j in n-1 downTo 0)
            lcp[i][j] = if (num[i] == num[j]) lcp[i+1][j+1]+1 else 0
        val dp = Array(n+1) { IntArray(n+1) }
        for (i in 1..n) {
            for (k in 1..i) {
                if (num[i-k] == '0') continue
                if (i-k == 0) { dp[i][k] = 1; continue }
                val j = i-k
                if (j-k >= 0) {
                    val cmp = lcp[j-k][i-k]
                    if (cmp >= k || num[j-k+cmp] <= num[i-k+cmp])
                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod
                }
                for (t in 1 until k) if (j-t >= 0)
                    dp[i][k] = (dp[i][k] + dp[j][t]) % mod
            }
        }
        var ans = 0
        for (k in 1..n) ans = (ans + dp[n][k]) % mod
        return ans
    }
}
 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

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        n, mod = len(num), 10**9+7
        if num[0] == '0': return 0
        lcp = [[0]*(n+1) for _ in range(n+1)]
        for i in range(n-1, -1, -1):
            for j in range(n-1, -1, -1):
                if num[i] == num[j]:
                    lcp[i][j] = lcp[i+1][j+1] + 1
        dp = [[0]*(n+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for k in range(1, i+1):
                if num[i-k] == '0': continue
                if i-k == 0:
                    dp[i][k] = 1
                    continue
                j = i-k
                if j-k >= 0:
                    cmp = lcp[j-k][i-k]
                    if cmp >= k or num[j-k+cmp] <= num[i-k+cmp]:
                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod
                for t in range(1, k):
                    if j-t >= 0:
                        dp[i][k] = (dp[i][k] + dp[j][t]) % mod
        return sum(dp[n][k] for k in range(1, n+1)) % mod
 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
33
34
35
36
37
38

impl Solution {
    pub fn number_of_combinations(num: String) -> i32 {
        let n = num.len();
        let modv = 1_000_000_007;
        let num = num.as_bytes();
        if num[0] == b'0' { return 0; }
        let mut lcp = vec![vec![0; n+1]; n+1];
        for i in (0..n).rev() {
            for j in (0..n).rev() {
                if num[i] == num[j] {
                    lcp[i][j] = lcp[i+1][j+1] + 1;
                }
            }
        }
        let mut dp = vec![vec![0; n+1]; n+1];
        for i in 1..=n {
            for k in 1..=i {
                if num[i-k] == b'0' { continue; }
                if i-k == 0 { dp[i][k] = 1; continue; }
                let j = i-k;
                if j >= k {
                    let cmp = lcp[j-k][i-k];
                    if cmp >= k || num[j-k+cmp] <= num[i-k+cmp] {
                        dp[i][k] = (dp[i][k] + dp[j][k]) % modv;
                    }
                }
                for t in 1..k {
                    if j >= t {
                        dp[i][k] = (dp[i][k] + dp[j][t]) % modv;
                    }
                }
            }
        }
        let mut ans = 0;
        for k in 1..=n { ans = (ans + dp[n][k]) % modv; }
        ans
    }
}
 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

class Solution {
    numberOfCombinations(num: string): number {
        const n = num.length, mod = 1_000_000_007
        if (num[0] === '0') return 0
        const lcp: number[][] = Array.from({length: n+1}, () => Array(n+1).fill(0))
        for (let i = n-1; i >= 0; i--)
            for (let j = n-1; j >= 0; j--)
                if (num[i] === num[j]) lcp[i][j] = lcp[i+1][j+1] + 1
        const dp: number[][] = Array.from({length: n+1}, () => Array(n+1).fill(0))
        for (let i = 1; i <= n; i++) {
            for (let k = 1; k <= i; k++) {
                if (num[i-k] === '0') continue
                if (i-k === 0) { dp[i][k] = 1; continue }
                const j = i-k
                if (j-k >= 0) {
                    const cmp = lcp[j-k][i-k]
                    if (cmp >= k || num[j-k+cmp] <= num[i-k+cmp])
                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod
                }
                for (let t = 1; t < k && j-t >= 0; t++)
                    dp[i][k] = (dp[i][k] + dp[j][t]) % mod
            }
        }
        let ans = 0
        for (let k = 1; k <= n; k++) ans = (ans + dp[n][k]) % mod
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of num. LCP and DP are both O(n^2).
  • 🧺 Space complexity: O(n^2), for the LCP and DP tables.