Code Implementation

MOD = 10**9 + 7

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1  # Base case: empty string has 1 way

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue  # Numbers can't have leading zeros
            num = 0
            for j in range(i, n):
                num = num * 10 + int(s[j])
                if num > k:
                    break
                dp[i] = (dp[i] + dp[j + 1]) % MOD
        return dp[0]
      

class Solution {
public:
    int numberOfArrays(string s, int k) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[n] = 1;

        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0') continue;
            long num = 0;
            for (int j = i; j < n; ++j) {
                num = num * 10 + (s[j] - '0');
                if (num > k) break;
                dp[i] = (dp[i] + dp[j + 1]) % MOD;
            }
        }
        return dp[0];
    }
};
      

class Solution {
    public int numberOfArrays(String s, int k) {
        int MOD = 1000000007;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1;

        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') continue;
            long num = 0;
            for (int j = i; j < n; ++j) {
                num = num * 10 + (s.charAt(j) - '0');
                if (num > k) break;
                dp[i] = (dp[i] + dp[j + 1]) % MOD;
            }
        }
        return dp[0];
    }
}
      

var numberOfArrays = function(s, k) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[n] = 1;

    for (let i = n - 1; i >= 0; --i) {
        if (s[i] === '0') continue;
        let num = 0;
        for (let j = i; j < n; ++j) {
            num = num * 10 + Number(s[j]);
            if (num > k) break;
            dp[i] = (dp[i] + dp[j + 1]) % MOD;
        }
    }
    return dp[0];
};
      

Problem Description

Given a string s consisting of digits and an integer k, you are asked to restore the array by splitting s into a sequence of integers, where:

• Each integer is between 1 and k (inclusive).
• No integer in the sequence has leading zeros.

Constraints:

• 1 <= s.length <= 10^5
• 1 <= k <= 10^9
• s does not contain leading zeros unless the number is zero itself.

Thought Process

The problem is about splitting a string of digits into valid numbers, making sure each is within a given range and does not have leading zeros. The naive way is to try every possible split, but with up to 10^5 digits, this would be far too slow.

Instead, we realize that for each position in the string, we can try forming numbers by taking one digit, two digits, and so on, until the number exceeds k or we hit a leading zero. For each valid split, we recursively count the number of ways to split the remaining string. This is a classic case for dynamic programming (DP), where we cache the results for each starting position to avoid redundant work.

Solution Approach

• Dynamic Programming Setup: We use a DP array dp[i] where dp[i] represents the number of ways to split the substring starting at index i.
• Base Case: dp[n] = 1, where n is the length of s. This means there's one way to split an empty string (do nothing).
• Transition: For each position i (from right to left), if s[i] is not '0', try all possible splits by taking substrings s[i:j+1] where the numeric value is ≤ k. For each valid split, add dp[j+1] to dp[i].
• Leading Zeros: If s[i] is '0', skip it because numbers cannot start with zero.
• Result: dp[0] gives the total number of ways to split the original string.
• Why DP? DP is used because the number of ways to split a substring depends only on the number of ways to split its suffixes, and the problem has overlapping subproblems. We use an array for fast O(1) lookups.
• Why Right-to-Left? We fill dp from the end because each state depends on future states (suffixes).

Example Walkthrough

Example: Let s = "1234" and k = 34.

• Start at index 0 (s[0] = '1'):
  • Take 1 digit: '1' (valid, ≤ 34), recurse on "234".
  • Take 2 digits: '12' (valid, ≤ 34), recurse on "34".
  • Take 3 digits: '123' (> 34), stop.
• For "234" (index 1):
  • '2' (valid), recurse on "34".
  • '23' (valid), recurse on "4".
  • '234' (> 34), stop.
• For "34" (index 2):
  • '3' (valid), recurse on "4".
  • '34' (valid), recurse on "" (empty, base case).
• For "4" (index 3):
  • '4' (valid), recurse on "" (base case).

Counting up the valid ways:

• "1" + "2" + "3" + "4"
• "1" + "2" + "34"
• "1" + "23" + "4"
• "12" + "3" + "4"
• "12" + "34"

Time and Space Complexity

• Brute-force: Tries all possible splits, leading to an exponential number of recursive calls, O(2ⁿ) in the worst case.
• Optimized DP:
  • For each position, we try at most log10(k) digits (since numbers must be ≤ k).
  • So, total time is O(n * log₁₀(k)).
  • Space is O(n) for the DP array.
• Why? Each substring is processed once, and for each, we only try up to the number of digits in k (at most 10 for k = 10^9).

Summary

The problem is a classic example of using dynamic programming to count the number of ways to partition a string under constraints. The key insight is to process the string from the end, using a DP array to store the number of ways to split each suffix. By only considering valid splits (no leading zeros, number ≤ k), and by leveraging the fact that large numbers of splits share subproblems, we achieve an efficient and elegant solution.