1416. Restore The Array

Problem Explanation

Suppose, we have a string containing digits and an integer k. We can restore the string to an array of integers, each being between [1, k] inclusive. There are some conditions:

1. All integers in the array are between [1, k] inclusive.
2. The array elements do not consist of leading zeros.
3. The sequence of array elements form the original string after stripping off the whitespaces.

Given these constraints, we have to find the number of various arrays that we can form and return that number % 10^9+7.

Let's walk through an example:

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

Here, the string is "1317" and k is 2000. Since the digits' sequence does not contain leading zeros and each possible integer formed from the sequence is between [1, k] inclusive, we can form 8 different arrays that satisfy the above conditions.

Approach

This problem uses a form of dynamic programming to solve it. The algorithm works with the idea of a dp array used to keep the different ways to restore parts of the original string, calling the function recursively to iterate through the string and break it down into possible integers within the range of 1 and k.

If there is an element in the dp array for the current index i, we skip to the next index. Otherwise, concatenating the current digit with the previously formed number if it is not greater than k and recursively call the function for subsequent digits. Finally, we store the results in the dp array to avoid processing the same data more than once.

It's essential since the sum might be very great, we will return the sum modulo 10^9 + 7, a common way in algorithmic questions to handle scenarios where the result could be huge.

Solution in Python

1
2python
3mod = 10 ** 9 + 7
4
5class Solution:
6    def numberOfArrays(self, s: str, k: int) -> int:
7        dp = [0] * (len(s) + 1)
8        dp[-1] = 1
9
10        for i in range(len(s) - 1, -1, -1):
11            dp[i], curr = 0, 0
12            for j in range(i, len(s)):
13                if curr == 0 and s[i] == '0':  # Leading zeros is not allowed
14                    break
15                curr = 10 * curr + int(s[j])
16                if curr > k:  # If it exceeds, end the inner loop
17                    break
18                dp[i] += dp[j + 1]
19                dp[i] %= mod
20
21        return dp[0]

In the Python solution, we are looping from the end of the string, and when we find a number curr that can be used, we add dp[j+1] to dp[i]. And finally, return the first value of dp which contains the result. The if curr == 0 and s[i] == '0': break condition is for the cases where there's a leading zero. We break the for loop when we encounter a leading zero.

Solution in Java

1
2java
3public int numberOfArrays(String s, int k) {
4    int n = s.length(), mod = (int)1e9+7;
5    int[] dp = new int[n + 1];
6    dp[n] = 1;  // base case
7    for (int i = n - 1; i >= 0; --i) {
8        long num = 0;
9        for (int j = i; j < n; ++j) {
10            if (j > i && s.charAt(i) == '0' || num > k) break;
11            num = num * 10 + s.charAt(j) - '0';
12            dp[i] = (dp[i] + dp[j + 1])%mod;
13        }
14    }
15    return dp[0];
16}

In the Java solution, we follow the same approach, but we have to take care of converting the character into an integer using s.charAt(j) - '0'.

Solution in JavaScript

1
2javascript
3const numberOfArrays = (s, k, pre = s.length, cache = {}) => {
4    if (pre in cache) {
5        return cache[pre];
6    }
7    if (pre === 0) {
8        return 1;
9    }
10    let count = 0;
11    for (let len = 1; pre - len >= 0; ++len) {
12        const num = Number(s.slice(pre - len, pre));
13        if (num > k) {
14            break;
15        }
16        if (num.toString().length !== len) {
17            continue;
18        }
19        count = (count + numberOfArrays(s, k, pre - len, cache)) % (1e9 + 7);
20    }
21    cache[pre] = count;
22    return count;
23};

In JavaScript, we convert the substring into an integer using Number(), continuing if a leading zero is present, increment count recursively, and store cache results for pruning.

Solution in C++

1
2C++
3const int MOD = 1e9+7;
4class Solution {
5public:
6    int numberOfArrays(string s, int k) {
7        int dp[100001] = {0};
8        int n= s.size();
9        dp[n] = 1;
10        for(int i = n-1; i >= 0; --i){
11            if(s[i] == '0') continue;
12            long long num = 0;
13            for(int j = i; j < n; ++j){
14                num = num*10 + (s[j] - '0');
15                if(num > k) break;
16                dp[i] = (dp[i] + dp[j+1]) % MOD;
17            }
18        }
19        return dp[0];
20    }
21};

In this C++ solution, we calculate the number by multiplying the prior number by 10 and add the current digit. If the number exceeds k, we stop processing.

Solution in C#

1
2C#
3public class Solution {
4    int[] dp;
5    int mod = 1000000000+7, k;
6    string s;
7    public int NumberOfArrays(string s, int k) {
8        if(s.Length == 1)
9            if(Convert.ToInt32(s) <= k)
10                return 1;
11            else
12                return 0;
13        this.k = k;
14        dp = new int[s.Length];
15        this.s = s;
16        return FindSolution(0);
17    }
18    
19    int FindSolution(int index) {
20        if(index >= s.Length)
21            return 1;
22        if(s[index] == '0')
23            return 0;
24        if(dp[index] != 0)
25            return dp[index];
26        int ans = 0, num = 0;
27        for(int i = index; i < s.Length; i++) {
28            num = num * 10 + (s[i] - '0');
29            if(num > k)
30                break;
31            ans = (ans + FindSolution(i+1)) % mod;
32        }
33        return dp[index] = ans;
34    }
35}

In C#, we are providing conditions to solve the problem with some constraints provided by this language.

Through this approach, we can figure out the different arrays that satisfy the conditions and constraints. With the dynamic programming approach and recursion, we have an efficient algorithm.## Key Takeaways

To solve this problem the Dynamic Programming Approach is an ideal strategy to utilize. This approach assists in avoiding unnecessary computations by storing intermediate results. In addition, recursion plays a pivotal role in breaking down the problem into simpler sub-problems.

Each solution provided above follows the same core logic. To summarize:

1. We declare a DP array, initialized with zeroes. The size of the array is the length of the string plus one. The last element in the array is set to one as the base case.

2. Iterating backwards, we calculate the total number for every substring within the range (that is equal to or less than k). We add the number of ways to get to the remaining part of the string (future substring) to the DP array at the current index.

3. In cases where the substring starts with zero or the number exceeds k, we break the loop.

4. For each valid substring, we add the DP value at the next index to the current index in the DP array.

5. In the end, we return the value at the first index of the DP array. This value gives us the total number of valid distinct arrays that can be formed from the string.

6. We utilize memoization to avoid computation of the same sub-problem again and again, improving efficiency.

Remember: Always handle edge cases like leading zeroes and keep the constraints in mind while developing your solution. Also, when the output can be very large, using modulo arithmetic can prevent integer overflow.

Also note that in different programming languages, the syntax to convert a string to an integer and vice versa may vary. Always be sure to make use of the correct syntax in the language of your choice.

Solution Implementation