Separate Numbers

In this approach, we can see that if any string starts with a 0 then it has no was to be separated into a list of non-decreasing positive integers.

Let's imagine we know the number of ways to split characters according to the rules before each position in the string and all possible lengths of the previous part. Then for the next position, the number of ways to split characters from start to this position can be calculated recursively.

And what if we know for each position in the string number of ways to split it into parts no longer than D. Then for D +1 we can calculate it from previous values for each position.

We will create a function ‘checkString(nums, start1, start2, length)’ which will check if the number formed by starting at ‘start1’ index is less than the number formed by starting at the ‘start2’ index, where both are of ‘length’ length

Algorithm:

• In the checkString(nums, start1, start2, length)
  • While ‘length’ is greater than 0
    • If ‘nums[start1]’ is less than ‘nums[start2]’ return True
    • If ‘nums[start2]’ is less than ‘nums[start1]’ return False.
    • Increase ‘start1’ and ‘start2’ by 1.
  • Return the ‘True’
• In the given function
  • Set ‘MOD’ as 10⁹ + 7
  • If nums[0]’ is ‘0’ return 0
  • If the length of ‘nums’ is 1 return 1
  • Set ‘n’ as the length of ‘nums’
  • Create two arrays of ‘n + 1’ lengths, ‘prev’ and ‘next’
  • Set ‘prev[0]’ and ‘next[0]’ as 1
  • Iterate ‘d’ from 1 to ‘n’
    • Copy all the values of ‘prev’ from index ‘1’ to ‘n’ into ‘next’
    • Iterate ‘j1’ from 0 to ‘n - d’
      • Set ‘j2’ as ‘j1’ - ‘d’, and i1 as ‘j1’ + ‘d’
      • If ‘nums’[j1]’ is ‘0’ continue the loop
      • If i1 is greater than ‘0’ or nums[i1] is not ‘0’ and checkString(nums, i1, j1, d)
        • Increase next[j2] by next[j1]
      • Otherwise
        • Increase next[j2] by prev[j1]
      • Set ‘next[j2]’ as ‘next[j2]’ mod ‘MOD’
  • Finally, return ‘prev[n]’

In this approach, we will use the idea behind the previous approach, which is if we know the number of ways to split characters according to the rules before each position in the string and all possible lengths of the previous part. Then for the next position, the number of ways to split characters from start to this position can be calculated.

Suppose the number of ways to form the list when the last number starts at index ‘i’ and ends at index ‘j’ is ‘dp[i][j]’.

Then ‘dp’ transition is Let length = j-i+1 = length of last number

Thus, we can choose all numbers ending at nums[i-1], and have length < length

=> dp[i][j] += dp[i-length+1][i-1] + ... + dp[i-1][i-1]

Now, if num[i-length : i-1] is smaller or equal to num[i : j]

i.e., if (second last number of length = length) is smaller or equal to last number, then

=> dp[i][j] += dp[i-length][i-1]

This is equal to the previous approach which is O(N ^ 3). To optimise it we Use prefix sum DP to calculate sums fast

Thus, in prefSum[i][j] we store dp[0][j] + dp[1][j] ... + dp[i][j]

We create a compare(i, j, length, same, nums), which will compare two strings fastly (O(1)). This is due to the ‘same’ matrix that stores the length of the common prefix for strings starting at ‘i’ and ‘j’

Algorithm:

• In the compare(i, j, length same, nums) function
  • Set ‘common’ as same[i][j]
  • If ‘common’ is greater than length return True
  • If ‘nums[common + i]’ is greater than ‘nums[common + j]’ return True
  • Otherwise, return False
• In the main function if nums[0] is ‘0’ return 0
• Set ‘n’ as the length of ‘nums’, Set ‘MOD’ as 10⁹ + 7
• Create a 2D matrix with 0’s of size nXn, called ‘same’
• Iterate i and j over every row and column index of ‘same’ in reverse order
  • If nums[i] is equal to nums[j]
    • Set same[i][j] equal to same[i + 1][j + 1] + 1
• Create a 2D matrix ‘prefSum’ of n + 1 X n + 1 dimensions
• Set the first row of ‘prefSum’ as all 0s
• Iterate i from 1 to n - 1
  • If ‘nums[i]’ is ‘0’ continue the loop
  • Iterate j from i to n - 1
    • Set length as ‘j - i + 1’, set ‘count’ as ‘0’ and set ‘prevStart’ as i - 1 - (length - 1)
    • If prevStart is less than 0
      • Set ‘count’ as prefSum[i - 1][j - 1]
    • Otherwise,
      • Set ‘count’ as ‘(prefSum[i - 1][i - 1] - prefSum[prevStart][i - 1])’
      • If compare(prevStart, i, length,same, nums) is True
        • Set ‘cnt’ as ‘prefSum[prevStart][i - 1]
        • If ‘prevStart’ is not 0 subtract prefSum[prevStart - 1][i - 1] from it
        • Add ‘cnt’ to ‘count’
      • Add ‘cnt’ to ‘count’
    • Set prefSum[i][j] as prefSum[i - 1][j - 1] + ‘count’
• Return the prefSum[n][n] % MOD