Number of Ways to Separate Numbers

Hard Dynamic Programming Strings Original on LeetCode

Number of Ways to Separate Numbers is a hard dynamic programming problem solved with the strings pattern. The best approach, optimal (dp with prefix sums + lcp table), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force dp (direct sums and string comparisons) up.

Problem

You wrote down a list of positive integers in non-decreasing order, then joined them with no separators, producing the digit string num. None of the integers had a leading zero.

Count how many different lists could have produced num. Since the count can be huge, return it modulo 10^9 + 7.

Examples

Example 1

Input
num = "1324"
Output
4
Why
The valid lists are [1324], [1, 324], [13, 24] and [1, 3, 24]. A split like [13, 2, 4] fails because 2 < 13.

Example 2

Input
num = "1050"
Output
2
Why
Only [1050] and [10, 50] work: any piece starting with the digit 0, such as "050" or "0", is not allowed.

Example 3

Input
num = "0123"
Output
0
Why
Whatever the split, the first number would start with 0.

Constraints

  • 1 <= num.length <= 3500
  • num contains only the digits 0-9.
  • Return the count modulo 10^9 + 7.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force DP (direct sums and string comparisons)O(n³)O(n²)
Optimal (DP with prefix sums + LCP table)O(n²)O(n²)

1Brute force DP (direct sums and string comparisons)

TimeO(n³)There are O(n²) states, and each one does an O(n) sum plus an O(n) substring comparison.
SpaceO(n²)The ways table has (n + 1) × (n + 1) entries.

Let ways[i][len] count valid lists for the prefix num[0..i) whose last number is the piece of length len ending at i. The last piece must not start with 0. If it is the whole prefix there is 1 way. Otherwise the previous piece ends at j = i - len and may be any shorter piece (sum those states), or a piece of the same length that is not larger (compare the two substrings).

  1. ways[i][len] = 0 if num[i - len] == '0'; = 1 if i == len.
  2. Otherwise j = i - len: add ways[j][k] for every k < len with k <= j.
  3. If j >= len and num[j - len..j) <= num[j..i) as strings, add ways[j][len].
  4. The answer is the sum of ways[n][len] over all len, all modulo 10^9 + 7.
class Solution {
    public int numberOfCombinations(String num) {
        final int MOD = 1_000_000_007;
        int n = num.length();
        long[][] ways = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int len = 1; len <= i; len++) {
                int j = i - len;
                if (num.charAt(j) == '0') continue;
                if (j == 0) { ways[i][len] = 1; continue; }
                long total = 0;
                for (int k = 1; k < len && k <= j; k++) total += ways[j][k];
                if (j >= len && num.substring(j - len, j).compareTo(num.substring(j, i)) <= 0) total += ways[j][len];
                ways[i][len] = total % MOD;
            }
        }
        long ans = 0;
        for (int len = 1; len <= n; len++) ans += ways[n][len];
        return (int) (ans % MOD);
    }
}

2Optimal (DP with prefix sums + LCP table)

TimeO(n²)The LCP table and the DP each fill O(n²) cells with O(1) work per cell.
SpaceO(n²)Two (n + 1) × (n + 1) tables.

Same states, but remove both O(n) inner costs. Keep pre[i][len] = ways[i][1] + … + ways[i][len], so 'any shorter previous piece' is a single lookup. Precompute lcp[a][b], the length of the longest common prefix of num[a..] and num[b..]; two equal-length pieces starting at a and b compare in O(1): if lcp >= len they are equal, otherwise the first differing digit decides.

  1. Build lcp from the back: lcp[a][b] = num[a] == num[b] ? lcp[a + 1][b + 1] + 1 : 0.
  2. For i = 1..n and len = 1..i with j = i - len: skip if num[j] == '0'; ways = 1 if j == 0.
  3. Otherwise ways = pre[j][min(len - 1, j)]; if j >= len, let l = lcp[j - len][j], and if l >= len or num[j - len + l] < num[j + l], add pre[j][len] - pre[j][len - 1].
  4. pre[i][len] = pre[i][len - 1] + ways (mod); the answer is pre[n][n].
class Solution {
    public int numberOfCombinations(String num) {
        final int MOD = 1_000_000_007;
        int n = num.length();
        char[] s = num.toCharArray();
        int[][] lcp = new int[n + 1][n + 1];
        for (int a = n - 1; a >= 0; a--)
            for (int b = n - 1; b > a; b--)
                if (s[a] == s[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
        int[][] pre = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int len = 1; len <= i; len++) {
                int j = i - len;
                long ways = 0;
                if (s[j] != '0') {
                    if (j == 0) ways = 1;
                    else {
                        ways = pre[j][Math.min(len - 1, j)];
                        if (j >= len) {
                            int l = lcp[j - len][j];
                            if (l >= len || s[j - len + l] < s[j + l])
                                ways += (pre[j][len] - pre[j][len - 1] + MOD) % MOD;
                        }
                    }
                }
                pre[i][len] = (int) ((pre[i][len - 1] + ways) % MOD);
            }
        }
        return pre[n][n];
    }
}

Edge cases to test

  • num starts with 0: answer 0
  • A single digit
  • Zeros in the middle, which can never begin a piece
  • Long runs of the same digit, where equal neighbouring pieces are allowed
  • Very long strings where the count overflows and must be taken modulo 10^9 + 7

Hints

Hint 1

Describe a state by where the last number ends and how long it is. What does the previous number need to satisfy?

Hint 2

If the previous number is shorter, it is automatically smaller (no leading zeros). If it has the same length, you must compare the two pieces digit by digit. If it is longer, it is too big.

Hint 3

Prefix sums over the length make the 'shorter' case O(1), and a longest-common-prefix table makes the equal-length comparison O(1).

FAQ

What is the best time complexity for Number of Ways to Separate Numbers?

Optimal (DP with prefix sums + LCP table) runs in O(n²) time and O(n²) extra space. The LCP table and the DP each fill O(n²) cells with O(1) work per cell.

Which pattern does Number of Ways to Separate Numbers use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.

Is there a brute force solution for Number of Ways to Separate Numbers?

Yes. Brute force DP (direct sums and string comparisons) takes O(n³) time and O(n²) space. Let ways[i][len] count valid lists for the prefix num[0..i) whose last number is the piece of length len ending at i.

Which edge cases should I test for Number of Ways to Separate Numbers?

num starts with 0: answer 0; A single digit; Zeros in the middle, which can never begin a piece; Long runs of the same digit, where equal neighbouring pieces are allowed; Very long strings where the count overflows and must be taken modulo 10^9 + 7.