# Number of Ways to Separate Numbers
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-separate-numbers)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-separate-numbers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String, Suffix Array
**Companies:** [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## 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 _the **number 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** `109 + 7`.

**Example 1:**

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

**Example 2:**

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

**Example 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'`.

# Approaches
## Brute-Force Backtracking
The most intuitive approach is to try all possible partitions of the number string `num` using recursion (backtracking). We can explore every possible way to split the string and, for each complete partition, check if it satisfies the given conditions: the sequence of numbers is non-decreasing and no number has a leading zero.
**Time:** O(2^n * n) · **Space:** O(n)
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient with a time complexity that is exponential.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.; Recalculates solutions for the same subproblems repeatedly.
### Explanation
We define a recursive helper function that explores all possible splits. This function takes the current starting index and the string representation of the previous number as parameters. It iterates through all possible endpoints for the current number, forming a substring. For each substring, it checks two conditions: validity (no leading zeros) and the non-decreasing property (the current number must be greater than or equal to the previous one). If the conditions are met, it makes a recursive call for the rest of the string. The sum of the results from these recursive calls gives the total number of ways for the current state. This method explores the entire search space of partitions, which grows exponentially with the length of the input string.

```java
class Solution {
    int n;
    String num;
    int MOD = 1_000_000_007;

    public int numberOfCombinations(String num) {
        this.num = num;
        this.n = num.length();
        if (num.charAt(0) == '0') {
            return 0;
        }
        // Using a 2D array for memoization would turn this into a DP solution.
        // Without it, it's pure backtracking.
        return backtrack(0, "");
    }

    private int backtrack(int startIndex, String prevNumStr) {
        if (startIndex == n) {
            return 1;
        }

        long totalWays = 0;
        for (int i = startIndex; i < n; i++) {
            String currentNumStr = num.substring(startIndex, i + 1);

            if (currentNumStr.length() > 1 && currentNumStr.charAt(0) == '0') {
                break; // Pruning
            }

            if (!prevNumStr.isEmpty()) {
                if (currentNumStr.length() < prevNumStr.length()) {
                    continue; // Pruning
                }
                if (currentNumStr.length() == prevNumStr.length() && currentNumStr.compareTo(prevNumStr) < 0) {
                    continue; // Pruning
                }
            }

            totalWays = (totalWays + backtrack(i + 1, currentNumStr)) % MOD;
        }
        return (int) totalWays;
    }
}
```
### Algorithm
- Define a recursive function `backtrack(startIndex, prevNumStr)` which returns the number of valid partitions for the suffix `num.substring(startIndex)` given the previous number was `prevNumStr`.
- **Base Case:** If `startIndex` reaches the end of the string, a valid partition has been found, so return 1.
- **Recursive Step:**
  - Initialize a counter `ways = 0`.
  - Iterate `i` from `startIndex` to the end of the string.
  - Form the `currentNumStr` from `startIndex` to `i`.
  - **Validation & Pruning:**
    - If `currentNumStr` has a leading zero (and is not just "0"), it's invalid. Since any longer string starting at `startIndex` will also have a leading zero, we can break the loop.
    - Compare `currentNumStr` with `prevNumStr`. If `currentNumStr` is smaller, this path is invalid, so we `continue` to the next iteration to form a larger number.
    - The comparison is done first by length, then lexicographically if lengths are equal.
  - If `currentNumStr` is valid, recursively call `backtrack(i + 1, currentNumStr)` and add the result to `ways`.
- The initial call is `backtrack(0, "")`.

## Dynamic Programming
This approach improves upon brute force by using dynamic programming to avoid recomputing results for overlapping subproblems. We define a 2D DP state `dp[i][j]` as the number of ways to partition the prefix `num[0...i-1]` where the last number has length `j`. The transition involves summing up the ways for all valid previous partitions. The main bottleneck is the string comparison needed in each DP state transition to enforce the non-decreasing constraint. A naive substring comparison takes O(length) time, leading to an overall time complexity of O(n^3).
**Time:** O(n^3) · **Space:** O(n^2)
**Pros:** Much more efficient than brute-force.; Systematic approach that guarantees correctness.; Introduces the DP structure that can be further optimized.
**Cons:** The O(n^3) complexity is too slow for the given constraints (`n <= 3500`).; The repeated substring creation and comparison is inefficient.
### Explanation
The core idea is to build up the solution for larger prefixes from the solutions for smaller prefixes. The state `dp[i][j]` represents the number of ways to partition `num`'s prefix of length `i` where the last number, `num.substring(i-j, i)`, has length `j`. To compute `dp[i][j]`, we look at the prefix of length `i-j`. The last number of any partition of this prefix, say of length `k`, must be less than or equal to our current number. We can optimize the summation over `k` by splitting the logic: when `k < j`, the previous number is always smaller. When `k == j`, we must perform a direct comparison. To make the summation part efficient, we use an auxiliary `prefixSum` table. `prefixSum[i][j]` stores the sum of `dp[i][k]` for `k` from 1 to `j`. This allows us to get the sum for shorter previous numbers in O(1) time. However, the comparison for same-length numbers still takes O(j) time, making the total complexity O(n^3).

```java
class Solution {
    public int numberOfCombinations(String num) {
        int n = num.length();
        int MOD = 1_000_000_007;

        if (num.charAt(0) == '0') {
            return 0;
        }

        int[][] dp = new int[n + 1][n + 1];
        int[][] prefixSum = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int start = i - j;
                if (num.charAt(start) == '0') {
                    dp[i][j] = 0;
                } else {
                    int prevEnd = start;
                    if (prevEnd == 0) {
                        dp[i][j] = 1;
                    } else {
                        int ways = 0;
                        // Case 1: Previous number is shorter
                        int maxPrevLen = Math.min(j - 1, prevEnd);
                        if (maxPrevLen > 0) {
                            ways = (ways + prefixSum[prevEnd][maxPrevLen]) % MOD;
                        }

                        // Case 2: Previous number has same length
                        if (prevEnd >= j) {
                            if (num.substring(prevEnd - j, prevEnd).compareTo(num.substring(start, i)) <= 0) {
                                ways = (ways + dp[prevEnd][j]) % MOD;
                            }
                        }
                        dp[i][j] = ways;
                    }
                }
                prefixSum[i][j] = (prefixSum[i][j - 1] + dp[i][j]) % MOD;
            }
        }

        return prefixSum[n][n];
    }
}
```
### Algorithm
- Let `dp[i][j]` be the number of ways to partition the prefix `num[0...i-1]` such that the last number has length `j`.
- Let `prefixSum[i][j]` be `sum(dp[i][k])` for `k` from 1 to `j`.
- Iterate `i` from 1 to `n` (prefix end) and `j` from 1 to `i` (last number length).
- The current number is `curr = num[i-j...i-1]`.
- If `curr` has a leading zero, `dp[i][j] = 0`.
- Otherwise, the previous number ended at `prevEnd = i-j`.
  - If `prevEnd == 0`, this is the first number, so `dp[i][j] = 1`.
  - If `prevEnd > 0`, we calculate `dp[i][j]` by summing up ways from valid previous partitions:
    1.  **Previous number is shorter:** Sum `dp[prevEnd][k]` for `k < j`. This is `prefixSum[prevEnd][min(j-1, prevEnd)]`.
    2.  **Previous number has same length:** If `prevEnd >= j`, compare `num[prevEnd-j...prevEnd-1]` with `curr`. If it's smaller or equal, add `dp[prevEnd][j]`.
- Update `prefixSum[i][j] = (prefixSum[i][j-1] + dp[i][j])`.
- The final answer is `prefixSum[n][n]`.

## Dynamic Programming with LCP Optimization
This approach optimizes the O(n^3) DP solution by accelerating the substring comparisons. The bottleneck in the previous approach was comparing two substrings of the same length, which took O(length) time. We can reduce this to O(1) by precomputing a Longest Common Prefix (LCP) table. The `lcp[i][j]` table stores the length of the common prefix between the suffixes of `num` starting at indices `i` and `j`. With this table, any two substrings of the same length can be compared in constant time. This optimization reduces the total time complexity from O(n^3) to O(n^2), which is efficient enough to pass within the time limits.
**Time:** O(n^2) · **Space:** O(n^2)
**Pros:** Highly efficient and passes for the given constraints.; Optimal solution for this problem.; Demonstrates a powerful optimization technique for string-based DP problems.
**Cons:** Requires more space for the LCP table.; Implementation is more complex due to the LCP precomputation step.
### Explanation
The overall DP structure remains the same as the O(n^3) approach. The key improvement is the elimination of the costly O(j) string comparison inside the inner loop. We first spend O(n^2) time to build an LCP table. `lcp[i][j]` can be computed with a simple DP relation: `lcp[i][j] = 1 + lcp[i+1][j+1]` if `num[i] == num[j]`, and 0 otherwise. We fill this by iterating `i` and `j` backwards from `n-1`.

Once the `lcp` table is ready, we can write a helper function `isLessOrEqual(start1, start2, len)` that performs the comparison in O(1). This function uses `lcp[start1][start2]` to find the first differing character and compares them. The main DP loops then proceed as before, but now each state transition takes O(1) time. The total time complexity is dominated by the O(n^2) LCP precomputation and the O(n^2) DP table filling.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private int[][] lcp;
    private String num;
    private int n;

    // Compares num.substring(start1, start1+len) and num.substring(start2, start2+len)
    private boolean isLessOrEqual(int start1, int start2, int len) {
        int common = lcp[start1][start2];
        if (common >= len) {
            return true; // Equal
        }
        return num.charAt(start1 + common) < num.charAt(start2 + common);
    }

    public int numberOfCombinations(String num) {
        this.num = num;
        this.n = num.length();
        if (num.charAt(0) == '0') {
            return 0;
        }

        // Precompute LCP array in O(n^2)
        lcp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (num.charAt(i) == num.charAt(j)) {
                    lcp[i][j] = 1 + lcp[i + 1][j + 1];
                }
            }
        }

        int[][] dp = new int[n + 1][n + 1];
        int[][] prefixSum = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int start = i - j;
                if (num.charAt(start) == '0') {
                    dp[i][j] = 0;
                } else {
                    int prevEnd = start;
                    if (prevEnd == 0) {
                        dp[i][j] = 1;
                    } else {
                        int ways = 0;
                        // Case 1: Previous number is shorter
                        int maxPrevLen = Math.min(j - 1, prevEnd);
                        if (maxPrevLen > 0) {
                            ways = (ways + prefixSum[prevEnd][maxPrevLen]) % MOD;
                        }

                        // Case 2: Previous number has same length (O(1) comparison)
                        if (prevEnd >= j) {
                            if (isLessOrEqual(prevEnd - j, start, j)) {
                                ways = (ways + dp[prevEnd][j]) % MOD;
                            }
                        }
                        dp[i][j] = ways;
                    }
                }
                prefixSum[i][j] = (prefixSum[i][j - 1] + dp[i][j]) % MOD;
            }
        }

        return prefixSum[n][n];
    }
}
```
### Algorithm
- **Precomputation:** Compute a 2D `lcp` table where `lcp[i][j]` is the length of the Longest Common Prefix of suffixes `num.substring(i)` and `num.substring(j)`. This takes O(n^2).
- **DP Calculation:** Use the same DP state `dp[i][j]` and `prefixSum` table as the O(n^3) approach.
- The transition logic is identical, but the comparison of same-length substrings is now optimized.
- To compare `num[start1...start1+len-1]` and `num[start2...start2+len-1]`, use the `lcp` table:
  - Get `common = lcp[start1][start2]`.
  - If `common >= len`, strings are equal.
  - Otherwise, they differ at `start1+common` and `start2+common`. Compare these characters.
- This comparison now takes O(1) time.
- The DP calculation, which was O(n^3), becomes O(n^2).
- The final answer is `prefixSum[n][n]`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int numberOfCombinations(String num) {
    int n = num.length();
    int[][] lcp = new int[n + 1][n + 1];
    for (int i = n - 1; i >= 0; --i) {
      for (int j = n - 1; j >= 0; --j) {
        if (num.charAt(i) == num.charAt(j)) {
          lcp[i][j] = 1 + lcp[i + 1][j + 1];
        }
      }
    }
    int[][] dp = new int[n + 1][n + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        int v = 0;
        if (num.charAt(i - j) != '0') {
          if (i - j - j >= 0) {
            int x = lcp[i - j][i - j - j];
            if (x >= j || num.charAt(i - j + x) >= num.charAt(i - j - j + x)) {
              v = dp[i - j][j];
            }
          }
          if (v == 0) {
            v = dp[i - j][Math.min(j - 1, i - j)];
          }
        }
        dp[i][j] = (dp[i][j - 1] + v) % MOD;
      }
    }
    return dp[n][n];
  }
}

```

### CPP

```cpp
class Solution { public: const int mod = 1e9 + 7 ; int numberOfCombinations ( string num ) { int n = num . size (); 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 ) { if ( num [ i ] == num [ j ]) { lcp [ i ][ j ] = 1 + lcp [ i + 1 ][ j + 1 ]; } } } auto cmp = [ & ]( int i , int j , int k ) { int x = lcp [ i ][ j ]; return x >= k || num [ i + x ] >= num [ j + x ]; }; vector < vector < int >> dp ( n + 1 , vector < int > ( n + 1 )); dp [ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 1 ; j <= i ; ++ j ) { int v = 0 ; if ( num [ i - j ] != '0' ) { if ( i - j - j >= 0 && cmp ( i - j , i - j - j , j )) { v = dp [ i - j ][ j ]; } else { v = dp [ i - j ][ min ( j - 1 , i - j )]; } } dp [ i ][ j ] = ( dp [ i ][ j - 1 ] + v ) % mod ; } } return dp [ n ][ n ]; } };
```

### Python

```python
class Solution : def numberOfCombinations ( self , num : str ) -> int : def cmp ( i , j , k ): x = lcp [ i ][ j ] return x >= k or num [ i + x ] >= num [ j + x ] mod = 10 ** 9 + 7 n = len ( num ) 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 ] = 1 + lcp [ i + 1 ][ j + 1 ] dp = [[ 0 ] * ( n + 1 ) for _ in range ( n + 1 )] dp [ 0 ][ 0 ] = 1 for i in range ( 1 , n + 1 ): for j in range ( 1 , i + 1 ): v = 0 if num [ i - j ] != '0' : if i - j - j >= 0 and cmp ( i - j , i - j - j , j ): v = dp [ i - j ][ j ] else : v = dp [ i - j ][ min ( j - 1 , i - j )] dp [ i ][ j ] = ( dp [ i ][ j - 1 ] + v ) % mod return dp [ n ][ n ]
```