Number of Ways to Separate Numbers
Number of Ways to Separate Numbers is a hard dynamic programming problem solved with the strings pattern.
The best approach, optimal (dp with prefix sums + lcp table), runs in O(n²) time and O(n²) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force dp (direct sums and string comparisons) up.
Problem
You wrote down a list of positive integers in non-decreasing order, then joined them with no separators, producing the digit string num. None of the integers had a leading zero.
Count how many different lists could have produced num. Since the count can be huge, return it modulo 10^9 + 7.
Examples
Example 1
- Input
num = "1324"- Output
4- Why
- The valid lists are [1324], [1, 324], [13, 24] and [1, 3, 24]. A split like [13, 2, 4] fails because 2 < 13.
Example 2
- Input
num = "1050"- Output
2- Why
- Only [1050] and [10, 50] work: any piece starting with the digit 0, such as "050" or "0", is not allowed.
Example 3
- Input
num = "0123"- Output
0- Why
- Whatever the split, the first number would start with 0.
Constraints
1 <= num.length <= 3500numcontains only the digits0-9.- Return the count modulo
10^9 + 7.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force DP (direct sums and string comparisons) | O(n³) | O(n²) |
| Optimal (DP with prefix sums + LCP table) | O(n²) | O(n²) |
1Brute force DP (direct sums and string comparisons)
O(n³)There are O(n²) states, and each one does an O(n) sum plus an O(n) substring comparison.O(n²)The ways table has (n + 1) × (n + 1) entries.Let ways[i][len] count valid lists for the prefix num[0..i) whose last number is the piece of length len ending at i. The last piece must not start with 0. If it is the whole prefix there is 1 way. Otherwise the previous piece ends at j = i - len and may be any shorter piece (sum those states), or a piece of the same length that is not larger (compare the two substrings).
- ways[i][len] = 0 if num[i - len] == '0'; = 1 if i == len.
- Otherwise j = i - len: add ways[j][k] for every k < len with k <= j.
- If j >= len and num[j - len..j) <= num[j..i) as strings, add ways[j][len].
- The answer is the sum of ways[n][len] over all len, all modulo 10^9 + 7.
class Solution {
public int numberOfCombinations(String num) {
final int MOD = 1_000_000_007;
int n = num.length();
long[][] ways = new long[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= i; len++) {
int j = i - len;
if (num.charAt(j) == '0') continue;
if (j == 0) { ways[i][len] = 1; continue; }
long total = 0;
for (int k = 1; k < len && k <= j; k++) total += ways[j][k];
if (j >= len && num.substring(j - len, j).compareTo(num.substring(j, i)) <= 0) total += ways[j][len];
ways[i][len] = total % MOD;
}
}
long ans = 0;
for (int len = 1; len <= n; len++) ans += ways[n][len];
return (int) (ans % MOD);
}
}class Solution:
def numberOfCombinations(self, num: str) -> int:
MOD = 10**9 + 7
n = len(num)
ways = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for ln in range(1, i + 1):
j = i - ln
if num[j] == '0':
continue
if j == 0:
ways[i][ln] = 1
continue
total = 0
for k in range(1, min(ln - 1, j) + 1):
total += ways[j][k]
if j >= ln and num[j - ln:j] <= num[j:i]:
total += ways[j][ln]
ways[i][ln] = total % MOD
return sum(ways[n]) % MODclass Solution {
public:
int numberOfCombinations(string num) {
const long long MOD = 1000000007LL;
int n = num.size();
vector<vector<long long>> ways(n + 1, vector<long long>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= i; len++) {
int j = i - len;
if (num[j] == '0') continue;
if (j == 0) { ways[i][len] = 1; continue; }
long long total = 0;
for (int k = 1; k < len && k <= j; k++) total += ways[j][k];
if (j >= len && num.compare(j - len, len, num, j, len) <= 0) total += ways[j][len];
ways[i][len] = total % MOD;
}
}
long long ans = 0;
for (int len = 1; len <= n; len++) ans += ways[n][len];
return (int)(ans % MOD);
}
};function numberOfCombinations(num) {
const MOD = 1000000007;
const n = num.length;
const ways = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let len = 1; len <= i; len++) {
const j = i - len;
if (num[j] === '0') continue;
if (j === 0) { ways[i][len] = 1; continue; }
let total = 0;
for (let k = 1; k < len && k <= j; k++) total = (total + ways[j][k]) % MOD;
if (j >= len && num.substring(j - len, j) <= num.substring(j, i)) total = (total + ways[j][len]) % MOD;
ways[i][len] = total;
}
}
let ans = 0;
for (let len = 1; len <= n; len++) ans = (ans + ways[n][len]) % MOD;
return ans;
}2Optimal (DP with prefix sums + LCP table)
O(n²)The LCP table and the DP each fill O(n²) cells with O(1) work per cell.O(n²)Two (n + 1) × (n + 1) tables.Same states, but remove both O(n) inner costs. Keep pre[i][len] = ways[i][1] + … + ways[i][len], so 'any shorter previous piece' is a single lookup. Precompute lcp[a][b], the length of the longest common prefix of num[a..] and num[b..]; two equal-length pieces starting at a and b compare in O(1): if lcp >= len they are equal, otherwise the first differing digit decides.
- Build lcp from the back: lcp[a][b] = num[a] == num[b] ? lcp[a + 1][b + 1] + 1 : 0.
- For i = 1..n and len = 1..i with j = i - len: skip if num[j] == '0'; ways = 1 if j == 0.
- Otherwise ways = pre[j][min(len - 1, j)]; if j >= len, let l = lcp[j - len][j], and if l >= len or num[j - len + l] < num[j + l], add pre[j][len] - pre[j][len - 1].
- pre[i][len] = pre[i][len - 1] + ways (mod); the answer is pre[n][n].
class Solution {
public int numberOfCombinations(String num) {
final int MOD = 1_000_000_007;
int n = num.length();
char[] s = num.toCharArray();
int[][] lcp = new int[n + 1][n + 1];
for (int a = n - 1; a >= 0; a--)
for (int b = n - 1; b > a; b--)
if (s[a] == s[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
int[][] pre = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= i; len++) {
int j = i - len;
long ways = 0;
if (s[j] != '0') {
if (j == 0) ways = 1;
else {
ways = pre[j][Math.min(len - 1, j)];
if (j >= len) {
int l = lcp[j - len][j];
if (l >= len || s[j - len + l] < s[j + l])
ways += (pre[j][len] - pre[j][len - 1] + MOD) % MOD;
}
}
}
pre[i][len] = (int) ((pre[i][len - 1] + ways) % MOD);
}
}
return pre[n][n];
}
}class Solution:
def numberOfCombinations(self, num: str) -> int:
MOD = 10**9 + 7
n = len(num)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for a in range(n - 1, -1, -1):
row, nxt, ca = lcp[a], lcp[a + 1], num[a]
for b in range(n - 1, a, -1):
if num[b] == ca:
row[b] = nxt[b + 1] + 1
pre = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
row = pre[i]
for ln in range(1, i + 1):
j = i - ln
ways = 0
if num[j] != '0':
if j == 0:
ways = 1
else:
pj = pre[j]
ways = pj[ln - 1 if ln - 1 < j else j]
if j >= ln:
l = lcp[j - ln][j]
if l >= ln or num[j - ln + l] < num[j + l]:
ways += pj[ln] - pj[ln - 1]
row[ln] = (row[ln - 1] + ways) % MOD
return pre[n][n]class Solution {
public:
int numberOfCombinations(string num) {
const int MOD = 1000000007;
int n = num.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
for (int a = n - 1; a >= 0; a--)
for (int b = n - 1; b > a; b--)
if (num[a] == num[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= i; len++) {
int j = i - len;
long long ways = 0;
if (num[j] != '0') {
if (j == 0) ways = 1;
else {
ways = pre[j][min(len - 1, j)];
if (j >= len) {
int l = lcp[j - len][j];
if (l >= len || num[j - len + l] < num[j + l])
ways += (pre[j][len] - pre[j][len - 1] + MOD) % MOD;
}
}
}
pre[i][len] = (int)((pre[i][len - 1] + ways) % MOD);
}
}
return pre[n][n];
}
};function numberOfCombinations(num) {
const MOD = 1000000007;
const n = num.length;
const s = new Uint8Array(n);
for (let i = 0; i < n; i++) s[i] = num.charCodeAt(i);
const lcp = Array.from({ length: n + 1 }, () => new Int32Array(n + 1));
for (let a = n - 1; a >= 0; a--)
for (let b = n - 1; b > a; b--)
if (s[a] === s[b]) lcp[a][b] = lcp[a + 1][b + 1] + 1;
const pre = Array.from({ length: n + 1 }, () => new Int32Array(n + 1));
for (let i = 1; i <= n; i++) {
for (let len = 1; len <= i; len++) {
const j = i - len;
let ways = 0;
if (s[j] !== 48) {
if (j === 0) ways = 1;
else {
ways = pre[j][Math.min(len - 1, j)];
if (j >= len) {
const l = lcp[j - len][j];
if (l >= len || s[j - len + l] < s[j + l])
ways += (pre[j][len] - pre[j][len - 1] + MOD) % MOD;
}
}
}
pre[i][len] = (pre[i][len - 1] + ways) % MOD;
}
}
return pre[n][n];
}Edge cases to test
- num starts with 0: answer 0
- A single digit
- Zeros in the middle, which can never begin a piece
- Long runs of the same digit, where equal neighbouring pieces are allowed
- Very long strings where the count overflows and must be taken modulo 10^9 + 7
Hints
Hint 1
Describe a state by where the last number ends and how long it is. What does the previous number need to satisfy?
Hint 2
If the previous number is shorter, it is automatically smaller (no leading zeros). If it has the same length, you must compare the two pieces digit by digit. If it is longer, it is too big.
Hint 3
Prefix sums over the length make the 'shorter' case O(1), and a longest-common-prefix table makes the equal-length comparison O(1).
FAQ
What is the best time complexity for Number of Ways to Separate Numbers?
Optimal (DP with prefix sums + LCP table) runs in O(n²) time and O(n²) extra space. The LCP table and the DP each fill O(n²) cells with O(1) work per cell.
Which pattern does Number of Ways to Separate Numbers use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Number of Ways to Separate Numbers?
Yes. Brute force DP (direct sums and string comparisons) takes O(n³) time and O(n²) space. Let ways[i][len] count valid lists for the prefix num[0..i) whose last number is the piece of length len ending at i.
Which edge cases should I test for Number of Ways to Separate Numbers?
num starts with 0: answer 0; A single digit; Zeros in the middle, which can never begin a piece; Long runs of the same digit, where equal neighbouring pieces are allowed; Very long strings where the count overflows and must be taken modulo 10^9 + 7.