#1416
Restore The Array
candidate master · 1510 · lc hard +32 · verified · 46.8% accepted · 1,668 likes · top 31%
Description
A program printed an integer array by concatenating all elements without spaces, producing the digit string s. Every element was in the range [1, k] with no leading zeros. Given s and k, count the number of distinct arrays that could have generated s. Return the answer 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]
Code
1
2
3