Number of Ways to Separate Numbers — Hard Problem & Solution

A list of positive integers was written down with no separators and no leading zeros, leaving the digit string num. The list was non-decreasing.

Difficulty: Hard
Topics: Strings, Dynamic Programming, Prefix Sum, Suffix Array
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A list of positive integers was written down with no separators and no leading zeros, leaving the digit string num. The list was non-decreasing.

Return how many such lists could have produced num, modulo 10⁹ + 7.

Example 1

Input: num = "327"
Output: 2
Explanation: `[327]` and `[3, 27]`. `[32, 7]` fails because 32 > 7.

Example 2

Input: num = "094"
Output: 0
Explanation: A leading zero is impossible.

Example 3

Input: num = "9999999999999"
Output: 101

Constraints

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

How to solve Number of Ways to Separate Numbers

Let dp[i][j] count the splits of num[0..j-1] whose last number occupies num[i..j-1]. Its predecessor num[p..i-1] is valid when it is shorter than the current number — automatic, since no number has a leading zero — or the same length and lexicographically no larger. The shorter case is a suffix-sum lookup; the equal case is one comparison, decided in O(1) by a longest-common-prefix table.

Approach

Return 0 if num begins with '0'.
Build lcp[a][b] = (num[a] == num[b]) ? lcp[a+1][b+1] + 1 : 0.
Process j from 1 to n. For each i < j with num[i] != '0', let L = j - i.
Add the suffix sum of dp[p][i] over p >= i - L + 1 — every predecessor strictly shorter than L.
If p = i - L is in range, compare num[p..i-1] with num[i..j-1] using lcp[p][i] and add dp[p][i] when it is no larger.
After finishing column j, build its suffix sums. The answer is the full column sum at j = n.

Why it works

Two observations make an O(n²) solution possible where a naive one is O(n³). First, a strictly shorter number is automatically smaller, because leading zeros are banned — so an entire range of predecessors needs no comparison at all, and a suffix sum collapses it to one lookup. Second, the only comparisons left are between equal-length substrings, and lcp answers each in constant time by finding the first position where they differ.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

A number may not begin with '0', which is exactly what licenses the "shorter implies smaller" shortcut.
The predecessor of equal length needs <=, not < — repeated values are allowed in a non-decreasing list.
The suffix sums for column j must be built only after every dp[i][j] is final.

Reference solution

Python

def numberOfCombinations(num: str) -> int:
    MOD = 10**9 + 7
    n = len(num)
    if num[0] == "0":
        return 0
    lcp = [[0] * (n + 1) for _ in range(n + 1)]
    for a in range(n - 1, -1, -1):
        for b in range(n - 1, -1, -1):
            lcp[a][b] = lcp[a + 1][b + 1] + 1 if num[a] == num[b] else 0
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    suf = [[0] * (n + 2) for _ in range(n + 1)]
    for j in range(1, n + 1):
        for i in range(j):
            if num[i] == "0":
                dp[i][j] = 0
                continue
            if i == 0:
                dp[0][j] = 1
                continue
            length = j - i
            lo = max(0, i - length + 1)
            total = suf[i][lo]
            p = i - length
            if p >= 0:
                c = lcp[p][i]
                if c >= length or num[p + c] < num[i + c]:
                    total = (total + dp[p][i]) % MOD
            dp[i][j] = total
        for p in range(j - 1, -1, -1):
            suf[j][p] = (suf[j][p + 1] + dp[p][j]) % MOD
    return suf[n][0]

JavaScript

var numberOfCombinations = function(num) {
    var MOD = 1000000007;
    var n = num.length, a, b, i, j, p;
    if (num.charAt(0) === "0") return 0;
    var grid = function(w) {
        var t = [];
        for (var x = 0; x <= n; x++) {
            var row = [];
            for (var y = 0; y < w; y++) row.push(0);
            t.push(row);
        }
        return t;
    };
    var lcp = grid(n + 1);
    for (a = n - 1; a >= 0; a--) {
        for (b = n - 1; b >= 0; b--) {
            lcp[a][b] = num.charAt(a) === num.charAt(b) ? lcp[a + 1][b + 1] + 1 : 0;
        }
    }
    var dp = grid(n + 1);
    var suf = grid(n + 2);
    for (j = 1; j <= n; j++) {
        for (i = 0; i < j; i++) {
            if (num.charAt(i) === "0") { dp[i][j] = 0; continue; }
            if (i === 0) { dp[0][j] = 1; continue; }
            var L = j - i;
            var lo = i - L + 1 > 0 ? i - L + 1 : 0;
            var total = suf[i][lo];
            p = i - L;
            if (p >= 0) {
                var c = lcp[p][i];
                if (c >= L || num.charAt(p + c) < num.charAt(i + c)) {
                    total = (total + dp[p][i]) % MOD;
                }
            }
            dp[i][j] = total;
        }
        for (p = j - 1; p >= 0; p--) suf[j][p] = (suf[j][p + 1] + dp[p][j]) % MOD;
    }
    return suf[n][0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue