Taro Logo

Restore The Array

#1 Most AskedHard
7 views
Topics:
StringsDynamic Programming

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is a piece that starts with zero illegal, even when the limit would otherwise allow that value?
  2. Is the limit inclusive, so a number equal to the limit is still valid?
  3. Should the number of arrays be reduced modulo one billion and seven?
  4. Can the limit force a piece to stop after a small number of digits?
  5. Does reaching the end of the digits count as one completed array?

Brute Force Solution

Approach

This recursion tries every place to end the next number, starting from the left. A branch dies when the next number would start with zero or grow larger than the limit. Each way of consuming the whole string contributes one, and every returned total is reduced by the modulus.

Here's how the algorithm would work step-by-step:

  1. If the start is at the end of the digits, return one completed way.
  2. If the digit at the start is zero, return zero ways.
  3. Otherwise grow a number one digit at a time from that start.
  4. Stop extending as soon as the number becomes larger than the limit.
  5. For each number that still fits, recurse on the suffix after it and add the returned ways.
  6. Reduce the summed ways by one billion and seven before returning them.
  7. Start the recursion at the first digit.

Code Implementation

class Solution:
    def numberOfArrays(self, digit_string: str, max_value: int) -> int:

        def count_valid_splits_from_index(start_index):
            # Base case: If we've successfully processed the entire string, we've found one valid way.
            if start_index == len(digit_string):
                return 1

            # A number cannot start with '0', so if the current substring does, it's an invalid split.
            if digit_string[start_index] == '0':
                return 0

            total_ways_from_this_point = 0
            current_number = 0

            # Iterate through all possible next numbers starting from the current position.
            for end_index in range(start_index, len(digit_string)):
                current_number = current_number * 10 + int(digit_string[end_index])

                # If the number formed exceeds the maximum allowed value, any longer number will also exceed it.
                if current_number > max_value:
                    break

                total_ways_from_this_point += count_valid_splits_from_index(end_index + 1)

            # The modulo is applied here as per problem constraints, though it's for large results.
            return total_ways_from_this_point % (10**9 + 7)

        return count_valid_splits_from_index(0)

Big(O) Analysis

Time Complexity
O(d^n) – From each start, the loop tries at most d endings, where d is the most digits a number can have without passing the limit. Each of those endings makes a fresh recursive call, and nothing remembers the answer for a suffix that has been seen before. The call tree therefore branches by up to d at every character along a string of length n. That tree is exponential, bounded by O(d^n). The modulus work inside a call is constant and does not change the bound.
Space Complexity
O(n) – There is no memoization table. Each recursive call stores the start, the growing number, and the running total, and a call consumes at least one digit before the next call. The deepest chain is therefore at most n frames, one per remaining digit. Those frames are released as the search backtracks. Extra space is the recursion stack, which is O(n).

Optimal Solution

Approach

This fill computes how many legal ways exist for every suffix, from the end of the digits backward. The end suffix has one way, an empty split. Each earlier start adds the ways of the suffixes that follow a number which fits under the limit and does not start with zero.

Here's how the algorithm would work step-by-step:

  1. Create an array of ways, one slot per suffix, and set the slot past the last digit to one.
  2. Walk the start index from the last digit back to the first.
  3. Leave a start at zero ways when its digit is zero.
  4. Otherwise grow the candidate number digit by digit while it stays within the limit.
  5. For each fitting number, add the already computed ways of the following suffix.
  6. Reduce that sum by one billion and seven as it is stored.
  7. Return the ways stored for the full string.

Code Implementation

class Solution:
    def numberOfArrays(self, digit_string: str, max_value: int) -> int:
        string_length = len(digit_string)
        modulus_value = 10**9 + 7

        # Memoization array to store results for subproblems, avoiding redundant calculations.
        # `ways_to_split[i]` will hold the number of valid ways to parse the suffix `digit_string[i:]`.
        ways_to_split = [0] * (string_length + 1)
        ways_to_split[string_length] = 1

        for start_index in range(string_length - 1, -1, -1):
            # If the current substring starts with '0', no valid number can be formed.
            if digit_string[start_index] == '0':
                continue

            current_number = 0
            for end_index in range(start_index, string_length):
                current_number = current_number * 10 + int(digit_string[end_index])

                # A number is valid only if it does not exceed the given maximum value.
                if current_number > max_value:
                    break

                # If a valid number is formed, add the number of ways the rest of the string can be split.
                ways_to_split[start_index] = (ways_to_split[start_index] + ways_to_split[end_index + 1]) % modulus_value

        return ways_to_split[0]

Big(O) Analysis

Time Complexity
O(n log k) – There is one start index for each of the n digits, and each suffix is solved only once. From a start, the inner loop adds digits only while the number stays within the limit k. A number larger than k has at most about the number of digits in k, which is logarithmic in k. Each inner step does a constant-time update of the ways. Multiplying n starts by a logarithmic inner bound gives O(n log k).
Space Complexity
O(n) – The ways array has one integer per suffix, including the empty suffix, so its length is n plus one. The scan keeps a start, an end, and the number being grown. It does not keep a two-dimensional table. The digit string is input. Extra space is O(n).

Edge Cases

The piece at the current start begins with zero
How to Handle:
Return zero ways from that start, because a number cannot have a leading zero.
The start index has reached the end of the digits
How to Handle:
Return one, because the digits have been fully split into a valid array.
Adding another digit would push the current number past the limit
How to Handle:
Stop lengthening that number, because every longer continuation is larger too.
The whole string is a single zero
How to Handle:
Return zero, because the only possible piece starts with zero.
Many cuts of one digit are valid
How to Handle:
Add the ways coming from each later suffix, and reduce the sum by the modulus.
The running total of ways exceeds the modulus
How to Handle:
Keep only the remainder modulo one billion and seven after combining suffix counts.
0/1 completed