Restore the array

String Dynamic Programming

46.8% acceptance

Feb 25, 2026

1667

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array. Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_arrays(s: String, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let k = k as i64;
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    // dp[i] = number of ways to partition s[0..i]
    let mut dp = vec![0i64; n + 1];
    dp[0] = 1;
    let max_digits = k.to_string().len();
    for i in 1..=n {
      // try all substrings s[j..i] as the last number
      for len in 1..=max_digits.min(i) {
        let j = i - len;
        if s[j] == b'0' { continue; } // no leading zeros
        // parse s[j..i] as number
        let mut num = 0i64;
        for &b in &s[j..i] {
          num = num * 10 + (b - b'0') as i64;
          if num > k { break; }
        }
        if num >= 1 && num <= k {
          dp[i] = (dp[i] + dp[j]) % MOD;
        }
      }
    }
    dp[n] as i32
  }
}