Restore The Array

Leetcode Daily Challenge (23rd April, 2023)

23 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/restore-the-array/description/

Problem Explanation with examples:-

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

Intuition:-

It is a partition DP problem. The dp[i] represents the number of ways to partition the string s[i:] into valid numbers in the range [1, k].
The dp[i] can be calculated by the sum of dp[j] where j is the index of the first character of the next valid number.
We iterate from the end of the string to the beginning. For each index i, we check if the substring s[i:j+1] is a valid number. If it is, we add dp[j+1] to dp[i].
The dp[0] is the final answer.

Solution:-

Initialize the dp array of size n+1 with all zeros.
Set dp[n] = 1 as there is only one way to partition the empty string.
Iterate from the end of the string to the beginning. If the current character is '0', we skip it as '0' cannot be the first digit of a valid number.
Otherwise, we set num = 0 and j = i. We iterate from j to the end of the string. If the substring s[i:j+1] is a valid number, we add dp[j+1] to num and increment j by 1.
After the inner loop, we set dp[i] = num % (10 ** 9 + 7).
Return dp[0].

Code:-

JAVA Solution

public class Solution {
    public int numberOfArrays(String s, int k) {
        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;
            }
            int num = 0;
            int j = i;
            while (j < n && Integer.parseInt(s.substring(i, j+1)) <= k) {
                num += dp[j+1];
                j++;
            }
            dp[i] = num % (10^9 + 7);
        }

        return dp[0];
    }
}

Python Solution

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[-1] = 1
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
            num = 0
            j = i
            while j < n and int(s[i:j+1]) <= k:
                num += dp[j+1]
                j += 1
            dp[i] = num % (10 ** 9 + 7)
        
        return dp[0]

Complexity Analysis:-

TIME:-

The time complexity of the code is O(n^2) where n is the length of the string s as we need to iterate through the string and check if the substring is a valid number.

SPACE:-

The space complexity of the code is O(n) where n is the length of the string s as we need to store the dp array.

References:-

Connect with me:-

java

python

leetcode

dsa