LeetCode 1977 - Number of Ways to Separate Numbers

The problem asks us to determine the number of ways a string of digits, num, can be split into a sequence of positive integers that are non-decreasing and have no leading zeros.

leetcodehardstringdynamic-programmingsuffix-array

LeetCode Problem 1977

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Suffix Array

Solution

Problem Understanding

The problem asks us to determine the number of ways a string of digits, num, can be split into a sequence of positive integers that are non-decreasing and have no leading zeros. Essentially, each valid partition represents a sequence of numbers that could have been originally written down before the commas were removed. The output is the total count of such sequences, modulo $10^9 + 7$, because the number of sequences could be very large.

The input num is a string of digits, and its length can be up to 3500 characters. This is important because it precludes any naive solution that enumerates all possible partitions, as the number of partitions grows exponentially with string length. Edge cases include strings with zeros at the start, single-digit strings, and sequences where all numbers are the same.

The constraints tell us:

  • Numbers cannot start with a '0'.
  • Numbers must be positive.
  • The sequence must be non-decreasing.
  • The string can be long, up to 3500 characters, so an efficient algorithm is required, likely O(n²) or better.

Key edge cases that can trip up a naive approach include:

  • Strings starting with '0' like "094".
  • Single-digit numbers, especially "0".
  • Strings where repeated numbers need careful comparison to maintain the non-decreasing property.

Approaches

Brute Force

The brute-force approach tries all possible partitions of the string. For each position, we decide whether to split the string there or not, recursively checking if the resulting numbers are non-decreasing and do not have leading zeros. Although this produces correct answers, it is extremely inefficient because the number of partitions grows exponentially with the string length. Specifically, a string of length n can have up to $2^{n-1}$ partitions, which is infeasible for n up to 3500.

Optimal Approach

The key insight is to use dynamic programming. We define dp[i] as the number of valid ways to partition the substring num[0:i]. To compute dp[i], we consider every possible last number that ends at index i-1, and we use a string comparison to ensure the non-decreasing property.

Because string comparison is costly, we can preprocess the longest common prefix (LCP) of all suffixes of the string. The LCP array allows us to efficiently check whether the last number is at least as large as the previous number without converting substrings to integers, which prevents overflow and optimizes the comparison.

This reduces the complexity from exponential to O(n²), which is feasible for n ≤ 3500.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively try all partitions, check each number validity
Optimal O(n²) O(n²) Dynamic programming with string comparison via LCP array

Algorithm Walkthrough

  1. Initialize a DP array dp of length n+1, where dp[i] represents the number of valid sequences for substring num[0:i]. Set dp[0] = 1 as the base case for an empty string.
  2. Precompute the longest common prefix (LCP) for all pairs of suffixes. LCP helps quickly determine if one substring is lexicographically less than, equal to, or greater than another substring.
  3. Iterate over the string from left to right. For each index i, try every possible start index j for the last number in the sequence such that num[j:i] does not start with '0'.
  4. For each candidate last number, compare it with the previous number using the LCP array. If the previous number is less than or equal to the last number, add dp[j] to dp[i].
  5. Apply modulo $10^9 + 7$ at each addition to prevent overflow.
  6. After iterating through the string, return dp[n], the number of valid partitions for the entire string.

Why it works:

The DP invariant is that dp[i] counts all valid partitions ending at i. By iterating over all possible last numbers and ensuring they are non-decreasing relative to the previous number, we guarantee that all sequences counted are valid. The LCP array ensures string comparison is efficient.

Python Solution

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        MOD = 10**9 + 7
        n = len(num)
        if num[0] == '0':
            return 0
        
        # Precompute LCP array
        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)
        dp[0] = 1
        
        for i in range(1, n+1):
            for j in range(i):
                if num[j] == '0':
                    continue
                length = i - j
                prev_start = j - length
                if prev_start >= 0:
                    common = lcp[prev_start][j]
                    if common < length and num[prev_start + common] > num[j + common]:
                        continue
                dp[i] = (dp[i] + dp[j]) % MOD
        
        return dp[n]

Explanation:

We first check for leading zero, which invalidates any sequence. Then we build the LCP array in reverse to allow fast comparison of any two substrings. dp is initialized with dp[0] = 1. For each ending index i, we consider all valid start indices j for the last number. If the number does not start with '0' and satisfies the non-decreasing property with the previous number, we add dp[j] to dp[i]. The final answer is dp[n].

Go Solution

func numberOfCombinations(num string) int {
    const MOD int = 1e9 + 7
    n := len(num)
    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)
    dp[0] = 1
    
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if num[j] == '0' {
                continue
            }
            length := i - j
            prevStart := j - length
            if prevStart >= 0 {
                common := lcp[prevStart][j]
                if common < length && num[prevStart+common] > num[j+common] {
                    continue
                }
            }
            dp[i] = (dp[i] + dp[j]) % MOD
        }
    }
    
    return dp[n]
}

Go-specific notes:

Slices are used instead of arrays. We explicitly initialize the 2D lcp slice. Integer overflow is avoided by using modulo at each addition. Indexing and comparisons follow the same logic as Python.

Worked Examples

Example 1: num = "327"

Step through DP:

i j num[j:i] dp[i]
1 0 "3" 1
2 0 "32" 1
2 1 "2" 0
3 0 "327" 1
3 1 "27" 1
3 2 "7" 0

Result: dp[3] = 2.

Example 2: num = "094"

Leading zero invalidates all sequences. dp[3] = 0.

Example 3: num = "0"

Single zero is invalid. dp[1] = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) We compute LCP in O(n²) and DP updates in O(n²)
Space O(n²) LCP array and DP array dominate space usage

Because n ≤ 3500, O(n²) is feasible. Each comparison is reduced to O(1) with the LCP array.

Test Cases

# Provided examples
assert Solution().numberOfCombinations("327") == 2  # multiple valid splits
assert Solution().numberOfCombinations("094") == 0