1416. Restore The Array

Hard

1.5K

48

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** `10`

.^{9} + 7

**Example 1:**

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

**Example 2:**

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

**Example 3:**

Input:s = "1317", k = 2000Output:8Explanation: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 <= 10`

^{5}`s`

consists of only digits and does not contain leading zeros.`1 <= k <= 10`

^{9}

Accepted

53.8K

Submissions

110.1K

Acceptance Rate

48.9%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved