We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Restore The Array

Number: 1517

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string of digits s (which was originally produced by concatenating integers from an array without spaces) and an integer k, count the number of ways to split s into a sequence of numbers where each number is between 1 and k and no number has extra leading zeros. Return the count modulo 10^9+7.

Key Insights

  • Use dynamic programming (DP) to count valid splits.
  • Define dp[i] as the number of ways to split the substring s[0:i].
  • Iterate over the string and, for each index, try forming valid numbers (while checking for leading zero and value <= k).
  • The maximum number of digits to form from any point is limited by the length of k (i.e. m=number of digits in k).

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the number of digits in k. Space Complexity: O(n), as we are using a DP array of size n+1.

Solution

The solution uses dynamic programming. We initialize a DP array (dp) where dp[0] is set to 1 (an empty split is one valid way). For each starting index i, we iterate over possible ending indices j (from i+1 to i+m, ensuring we don't go out of bounds) forming a substring. If the substring starting with a non-zero digit represents an integer value that is <= k, then we add dp[i] to dp[j]. If a substring starts with '0', we break out of the inner loop since any number with a leading zero is invalid. Finally, dp[n] gives the number of valid ways to split s. Modulo operations are performed at each addition to handle large numbers.

Code Solutions

# Python solution for "Restore The Array"
MOD = 10**9 + 7

def number_of_arrays(s: str, k: int) -> int:
    n = len(s)
    dp = [0] * (n + 1)  # dp[i] stores the number of ways to split s[0:i]
    dp[0] = 1  # Base case: an empty string has one way to be segmented
    
    # Precompute the maximum length of a number (digits) we should consider
    max_len = len(str(k))
    
    # Iterate over each possible starting index for a number
    for i in range(n):
        if s[i] == '0':  # Skip, because numbers in our array cannot have leading zeros.
            continue
        num = 0
        # Try to extend the number from position i to j
        for j in range(i, min(n, i + max_len)):
            num = num * 10 + int(s[j])  # Build the number digit by digit
            if num > k:
                break  # Further extension will only make the number larger than k
            dp[j + 1] = (dp[j + 1] + dp[i]) % MOD  # Update dp for the substring ending at j
    return dp[n]

# Example usage:
print(number_of_arrays("1000", 10000))  # expected output: 1
print(number_of_arrays("1000", 10))     # expected output: 0
print(number_of_arrays("1317", 2000))   # expected output: 8
← Back to All Questions