Number of ways to separate numbers

String Dynamic Programming Suffix Array

21.6% acceptance

Feb 25, 2026

536

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_combinations(num: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let s = num.as_bytes();
    let n = s.len();
    
    if s[0] == b'0' {
      return 0;
    }
    
    // lcp[i][j] = length of longest common prefix of s[i..] and s[j..]
    let mut lcp = vec![vec![0usize; n + 1]; n + 1];
    for i in (0..n).rev() {
      for j in (0..n).rev() {
        if s[i] == s[j] {
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
      }
    }
    
    // compare s[a..a+len] vs s[b..b+len] lexicographically
    // returns true if s[a..a+len] <= s[b..b+len]
    let le = |a: usize, b: usize, len: usize| -> bool {
      let common = lcp[a][b].min(len);
      if common == len {
        return true; // equal
      }
      s[a + common] <= s[b + common]
    };
    
    // dp[i][j] = number of ways to partition s[0..=i] where the last number has length j
    // This means the last number is s[i-j+1..=i]
    // Prefix sum optimization: pdp[i][j] = sum of dp[i][k] for k = 1..j
    
    let mut dp = vec![vec![0i64; n + 1]; n];
    let mut pdp = vec![vec![0i64; n + 1]; n];
    
    // Base: the first number starts at index 0 with length (i+1)
    for i in 0..n {
      let len = i + 1;
      if s[0] != b'0' {
        dp[i][len] = 1;
      }
    }
    
    // Fill dp
    for i in 0..n {
      for j in 1..=i + 1 {
        // last number is s[i-j+1..=i] with length j
        let start = i + 1 - j;
        if s[start] == b'0' {
          // leading zero, skip
          dp[i][j] = 0;
        } else if start > 0 {
          // previous number ends at start-1
          // previous number length k, the number before last ends at start-1
          // We need: prev number <= current number
          // prev number starts at start-k, has length k
          // If k < j: always <= (shorter number is smaller if no leading zeros)
          // If k == j: need s[start-k..start-1] <= s[start..i]
          // If k > j: always > 
          
          // Sum of dp[start-1][k] for k=1..j-1 (always valid since shorter)
          // plus dp[start-1][j] if s[start-j..start-1] <= s[start..i]
          
          let prev_end = start - 1;
          // sum for k=1..j-1
          let mut val = if j >= 2 { pdp[prev_end][j - 1] } else { 0 };
          
          // check k == j
          if start >= j {
            let prev_start = start - j;
            if le(prev_start, start, j) {
              val = (val + dp[prev_end][j]) % MOD;
            }
          }
          
          dp[i][j] = val % MOD;
        }
      }
      // compute prefix sums
      pdp[i][0] = 0;
      for j in 1..=n {
        pdp[i][j] = (pdp[i][j - 1] + dp[i][j]) % MOD;
      }
    }
    
    let mut ans = 0i64;
    for j in 1..=n {
      ans = (ans + dp[n - 1][j]) % MOD;
    }
    ans as i32
  }
}