C++     Dynamic Programming     Hard     Memoization     Recursion     String    

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.

 

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:

Here is a baseline solution that works for small test cases.

 
int numberOfArrays(string s, int k, int i=0) 
{
    if (i==s.length()) return 1;
    if (s[i]=='0') return 0;
    int j = i, res=0;
    string cur = "";
    while(j<s.length())
    {
        cur.push_back(s[j]);
        if (stoi(cur)>k) break;
        res += numberOfArrays(s, k, ++j);
    }
    return res;
}

Now let us add memoization, add limits and mod the answer.

 
int mod = 1e9+7;
int dfs(string &s, int k, int i, vector<int>&memo)
{
    if (i==s.length()) return 1;
    if (memo[i]!=-1) return memo[i];
    if (s[i]=='0') return 0;
    int j = i, res=0;
    string cur = "";
    while(j<s.length())
    {
        cur.push_back(s[j]);
        if (cur.length()>=11 || ((cur.length()==10 && s[i]>'1')) || stoi(cur)>k) break;
        res += dfs(s, k, ++j, memo)%mod;
        res %=mod;
    }
    return memo[i] = res;
}
int numberOfArrays(string s, int k) 
{
    vector<int> memo(s.length(),-1);
    return dfs(s, k, 0, memo);
}

Analysis: $O(m\log(k))$ TC, $O(m)$ SC where $m=\vert s \vert$.