Number of Ways to Separate Numbers: DP with LCP Optimization

You are given a string of digits num. You need to find the number of ways to split it into non-empty substrings such that each resulting number has no leading zeros and each number (except the first) is greater than or equal to the one before it. Return the answer modulo 10^9 + 7.

This is LeetCode 1977: Number of Ways to Separate Numbers. For example, num = "327" has 2 valid separations: [3, 27] and [327]. The split [32, 7] fails because 32 > 7, and [3, 2, 7] fails because 3 > 2.

If you have solved Decode Ways or Palindrome Partitioning, you have seen string partition DP before. This problem takes it further by requiring you to compare numeric values across partitions, and doing that comparison efficiently is the core challenge.

Why this problem matters

Most string partition DP problems let you check each substring independently. In Decode Ways, you check whether one or two digits form a valid letter code. In palindrome problems, you check whether a substring reads the same forwards and backwards. Neither requires you to compare one partition against the next.

Number of Ways to Separate Numbers does. Each number must be greater than or equal to the previous one, which means every DP transition needs a comparison between two substrings interpreted as integers. Doing that comparison naively takes O(n) time per pair, pushing the overall solution to O(n^3). The key optimization, using a precomputed longest common prefix (LCP) table, drops each comparison to O(1) and brings the total to O(n^2).

This problem teaches you a technique that appears in many advanced string DP problems: precomputing auxiliary information to speed up substring comparisons.

The key insight

Define dp[i][j] as the number of valid partitions of num[1..i] where the last number starts at position j. The last number is the substring num[j..i], and the previous number must end at position j-1.

For a transition to be valid, the previous number (ending at j-1) must satisfy two conditions: it must have no leading zeros, and it must be less than or equal to num[j..i].

Comparing two numbers as integers requires care. If the previous number is shorter than the current one, it is automatically smaller. If both have the same length, you need to compare them digit by digit. This is where the LCP array comes in.

Build a 2D table lcp[i][j] that stores the length of the longest common prefix between num[i..] and num[j..]. You can fill this table in O(n^2) time by working backwards: if num[i] == num[j], then lcp[i][j] = lcp[i+1][j+1] + 1; otherwise lcp[i][j] = 0.

With this table, comparing two substrings of equal length L starting at positions p and q takes O(1). If lcp[p][q] >= L, the two substrings are identical (and the condition holds). Otherwise, compare the single character at position p + lcp[p][q] versus q + lcp[p][q].

To further optimize, use prefix sums over each column of the DP table so that summing over all valid start positions for the previous number is O(1) instead of O(n).

The solution

def numberOfCombinations(num):
    MOD = 10**9 + 7
    n = len(num)
    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
            else:
                lcp[i][j] = 0

    def compare(p, q, length):
        common = min(lcp[p][q], length)
        if common >= length:
            return 0
        return -1 if num[p + common] < num[q + common] else 1

    dp = [[0] * n for _ in range(n)]
    prefix = [[0] * (n + 1) for _ in range(n)]

    for i in range(n):
        if num[0] == '0':
            dp[i][0] = 0
        else:
            dp[i][0] = 1
        prefix[i][0] = 0
        prefix[i][1] = dp[i][0]

    for j in range(1, n):
        for i in range(j, n):
            dp[i][j] = 0
            if num[j] == '0':
                prefix[j][i - j + 2] = prefix[j][i - j + 1]
                continue
            cur_len = i - j + 1
            prev_end = j - 1
            prev_start_min = prev_end - cur_len + 1

            if prev_start_min >= 0:
                cmp = compare(prev_start_min, j, cur_len)
                if cmp <= 0:
                    dp[i][j] = prefix[prev_end][prev_end - prev_start_min + 1] % MOD
                else:
                    dp[i][j] = (prefix[prev_end][prev_end - prev_start_min] if prev_end - prev_start_min >= 0 else 0) % MOD
            else:
                dp[i][j] = prefix[prev_end][prev_end + 1] % MOD

            dp[i][j] %= MOD
            prefix[j][i - j + 2] = (prefix[j][i - j + 1] + dp[i][j]) % MOD

    result = 0
    for j in range(n):
        result = (result + dp[n - 1][j]) % MOD
    return result

The solution has three main components. First, it builds the LCP table in O(n^2) by comparing suffixes of the string from right to left. Second, it fills the DP table where dp[i][j] counts partitions ending at position i with the last number starting at position j. Third, it maintains prefix sums so that summing over valid previous start positions is O(1).

The compare function is the heart of the optimization. Given two substring positions and a length, it uses the precomputed LCP table to determine which substring is larger without scanning digit by digit. If the common prefix covers the entire length, the substrings are equal. Otherwise, a single character comparison settles it.

For each cell dp[i][j], you need to know: among all ways to partition num[1..j-1] where the last number has length at most cur_len (and if exactly cur_len, is numerically less than or equal to num[j..i]), how many are there? The prefix sums over columns give you this aggregate in O(1).

Visual walkthrough

Let's trace through the DP construction for num = "1324".

The crucial moment is computing dp[4][3], where the last number is "24" and we need to check all valid previous numbers ending at position 2. The previous number "3" has length 1, which is less than length 2, so it is automatically valid. The previous number "13" has length 2, equal to "24". The LCP of "13" and "24" starting at their respective positions is 0 (first digits differ), and since "1" < "2", we know "13" < "24". Both predecessors contribute, giving dp[4][3] = 2.

Complexity analysis

Time: Building the LCP table takes O(n^2). Filling the DP table takes O(n^2) because each cell is filled in O(1) using prefix sums and the LCP table. The total is O(n^2).

Space: Both the LCP table and the DP table (with prefix sums) are n x n, giving O(n^2) space.

Edge cases

• Leading zeros: If num[0] == '0', the answer is 0 immediately. Within the DP, any substring starting with '0' is invalid and contributes 0.
• Single digit: A string like "5" has exactly 1 valid partition.
• All same digits: A string like "1111" has many valid partitions because every non-decreasing sequence of identical digits works. The count grows combinatorially.
• Very long strings: With n up to 3500 in the constraints, an O(n^2) solution is necessary. O(n^3) will not pass.
• Modular arithmetic: The answer can be astronomically large, so every addition must be taken mod 10^9 + 7.

The building blocks

This problem combines two reusable building blocks.

1. Substring DP partition. Define dp[i][j] to track partitions of a prefix where the last segment starts at j and ends at i. This pattern appears whenever you split a string into pieces and need to track properties of the last piece.

for j in range(1, n):
    for i in range(j, n):
        cur_len = i - j + 1
        dp[i][j] = aggregate_of_valid_predecessors(j - 1, cur_len)

2. LCP comparison array. Precompute the longest common prefix between every pair of suffixes to enable O(1) substring comparison.

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 s[i] == s[j]:
            lcp[i][j] = lcp[i + 1][j + 1] + 1
        else:
            lcp[i][j] = 0

Common mistakes

• Forgetting leading zeros. A substring starting with '0' is not a valid number (unless the problem says otherwise). You must skip these entries in the DP.
• Comparing numbers as strings without length check. The string "9" is numerically less than "10", but lexicographically greater. Always compare lengths first; only compare digits when lengths are equal.
• Missing prefix sums. Without prefix sums on the DP columns, summing over valid predecessors takes O(n) per cell, making the total O(n^3).
• Off-by-one in LCP indexing. The LCP table uses 0-indexed suffix positions. Mixing 0-indexed and 1-indexed positions in the DP is a common source of bugs.
• Forgetting the modulo. With large inputs, intermediate sums overflow without modular arithmetic applied at every addition.

From understanding to recall

You now know the three-layer structure of this solution: the LCP precomputation, the DP recurrence, and the prefix sum optimization. Each layer is conceptually simple on its own. The LCP table is a standard suffix comparison tool. The DP recurrence follows the familiar partition template. The prefix sums are a standard aggregation trick.

What makes this problem hard is assembling all three layers correctly. The LCP table feeds into the comparison function, which gates the DP transitions, which are accelerated by prefix sums. Missing any one layer breaks the solution.

The best way to internalize this is to practice each building block separately until it is automatic, then combine them. The substring partition DP shows up in problems like Decode Ways and palindrome partitioning. The LCP array shows up in suffix array problems. The prefix sum optimization shows up in any DP where you need to aggregate over a range of prior states.

The CodeBricks system breaks problems like this into their component building blocks and drills each one with spaced repetition. Once you can write the LCP table, the partition DP, and the prefix sum optimization from memory, assembling them under interview pressure becomes manageable.

Related posts

• Decode Ways - String partitioning DP with validity constraints
• Palindrome Partitioning - Partitioning a string with substring property checks
• Distinct Subsequences - Advanced string DP with careful state transitions

Ready to master advanced DP patterns like LCP-optimized partitioning? CodeBricks gives you targeted practice on the building blocks behind problems like this, with spaced repetition to make the patterns stick.