{x}
blog image

Restore The Array

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.

 

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only digits and does not contain leading zeros.
  • 1 <= k <= 109

Solution Explanation for Restore The Array

This problem asks to find the number of ways to partition a string s of digits into integers such that each integer is within the range [1, k]. This is a classic dynamic programming problem.

Approach:

We can use dynamic programming to solve this problem efficiently. Let dp[i] represent the number of ways to partition the substring s[0...i]. We iterate through the string, and for each position i, we consider all possible integers that can end at position i.

For each potential integer num ending at index i, we check:

  1. Validity: Is num within the range [1, k]?
  2. Leading Zero: Does num start with a '0' (except for the case where num is just '0')?

If both conditions are true, we add dp[j] (where j is the index before the start of num) to dp[i]. This is because dp[j] represents the number of ways to partition the substring before num, and we can append num to any of these partitions.

Base Case: dp[0] = 1 (empty partition).

Time Complexity: O(n*log₁₀(k)), where n is the length of the string s. The log₁₀(k) factor comes from the maximum number of digits in a valid integer. In the worst case, we examine almost every possible substring as a potential number.

Space Complexity: O(n), where n is the length of the string s, due to the dp array.

Code (Python):

def restoreArray(s, k):
    n = len(s)
    mod = 10**9 + 7
    dp = [0] * (n + 1)
    dp[0] = 1
 
    for i in range(1, n + 1):
        for j in range(max(0, i - 10), i): #consider at most 10 digits for num
            num = int(s[j:i])
            if 1 <= num <= k and (j == i - 1 or s[j] != '0'):
                dp[i] = (dp[i] + dp[j]) % mod
    return dp[n]

Code (Java):

public int restoreArray(String s, int k) {
    int n = s.length();
    long[] dp = new long[n + 1];
    dp[0] = 1;
    long mod = 1000000007;
 
    for (int i = 1; i <= n; i++) {
        for (int j = Math.max(0, i - 10); j < i; j++) {
            long num = Long.parseLong(s.substring(j, i));
            if (num >= 1 && num <= k && (j == i - 1 || s.charAt(j) != '0')) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
    }
    return (int) dp[n];
}

Code (C++):

int restoreArray(string s, long long k) {
    int n = s.length();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    long long mod = 1e9 + 7;
 
    for (int i = 1; i <= n; ++i) {
        for (int j = max(0, i - 10); j < i; ++j) {
            long long num = stoll(s.substr(j, i - j));
            if (num >= 1 && num <= k && (j == i - 1 || s[j] != '0')) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
    }
    return dp[n];
}

Code (Go):

func restoreArray(s string, k int) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	mod := 1000000007
 
	for i := 1; i <= n; i++ {
		for j := max(0, i-10); j < i; j++ {
			num, err := strconv.Atoi(s[j:i])
			if err != nil {
				continue
			}
			if num >= 1 && num <= k && (j == i-1 || s[j] != '0') {
				dp[i] = (dp[i] + dp[j]) % mod
			}
		}
	}
	return dp[n]
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These codes implement the dynamic programming solution described above. Remember to handle the modulo operation to prevent integer overflow. The max function in the Go code is a helper function to ensure that j does not go out of bounds.