Number of Ways to Separate Numbers - Solution & Explanation
Problem Statement
You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was non-decreasing and that no integer had leading zeros.
Return the number of possible lists of integers that you could have written down to get the string num. Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: num = "327" Output: 2 Explanation: You could have written down the numbers: 3, 27 327
Example 2:
Input: num = "094" Output: 0 Explanation: No numbers can have leading zeros and all numbers must be positive.
Example 3:
Input: num = "0" Output: 0 Explanation: No numbers can have leading zeros and all numbers must be positive.
Constraints:
1 <= num.length <= 3500numconsists of digits'0'through'9'.
Approach Overview
Problem Overview: You receive a numeric string and must count how many ways it can be split into a sequence of integers where each number is non‑decreasing compared to the previous one. Leading zeros are not allowed. The challenge is comparing many substrings efficiently while exploring valid partitions.
Approach 1: Recursive Approach with Memoization (Exponential → Pruned with DP)
This approach treats the problem as recursive partitioning of the string. At each index, choose a substring representing the next number and verify two rules: it cannot start with '0', and it must be greater than or equal to the previous number. The recursion continues from the next index. Memoization stores results based on the current index and previous substring length so repeated states are not recomputed. Even with caching, substring comparisons can be expensive, and the number of candidate splits grows quickly. Time complexity is roughly O(n^3) in the worst case due to substring comparisons, and space complexity is O(n^2) for memoization states and recursion stack. This method helps build intuition for how the partitioning works.
Approach 2: Dynamic Programming with Fast String Comparison (Optimal)
The optimized approach uses dynamic programming combined with precomputed substring comparison. Let dp[i][len] represent the number of valid ways to form a sequence ending at index i where the last number has length len. For each candidate number ending at i, you compare it with the previous number of the same or smaller length to ensure the non‑decreasing condition. Direct string comparison would make the solution too slow, so an LCP (longest common prefix) table is precomputed. This idea is closely related to structures used in suffix arrays and enables constant‑time substring comparison.
With LCP values, you can determine whether two substrings are lexicographically ordered without scanning characters repeatedly. Prefix sums over DP states allow fast transitions when the previous number length is smaller. Each position processes possible lengths while enforcing the no‑leading‑zero rule. The final answer is the sum of valid sequences that consume the entire string.
This reduces the overall complexity to O(n^2) time and O(n^2) space. The algorithm relies heavily on string processing and dynamic programming state transitions, which makes it the expected solution for this hard problem.
Recommended for interviews: Start by describing the recursive partition idea to show you understand the constraints and ordering rule. Then move to the dynamic programming solution with LCP‑based substring comparison. Interviewers typically expect the optimized O(n^2) DP approach because it demonstrates strong control over string comparison, state design, and performance optimization.
Approach 1: Dynamic Programming with String Comparison
This approach involves using dynamic programming to solve the problem efficiently. We use a 2D DP table where dp[i][j] indicates the number of ways to partition the string from position i to j. We'll iterate over each possible partitioning point, using string comparison to ensure non-decreasing order without leading zeros.
In this C solution, we use a single DP array where dp[i] is the number of ways to partition the string up to i. We update this array by iterating over previous partitions and ensuring string segments are valid. A copy of the DP array helps manage operations without affecting the current state.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 2: Recursive Approach with Memoization
This approach leverages recursion with memoization to solve the problem efficiently. We go through the number string recursively, attempting to partition it and storing intermediate results to avoid redundant calculations.
This C solution implements a recursive function `helper` that explores all ways of parting the string. It utilizes memoization to avoid redundant calculations, storing results in `mem`. We use string copying and comparison for validating partitions.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 3: Dynamic Programming + Prefix Sum
Define dp[i][j] to represent the number of ways to partition the first i characters of the string num such that the length of the last number is j. Clearly, the answer is sum_{j=0}^{n} dp[n][j]. The initial value is dp[0][0] = 1.
For dp[i][j], the end of the previous number should be i-j. We can enumerate dp[i-j][k], where k \le j. For the part where k < j, i.e., the number of ways with a length less than j can be directly added to dp[i][j], i.e., dp[i][j] = sum_{k=0}^{j-1} dp[i-j][k]. Because the previous number is shorter, it means it is smaller than the current number. Here, prefix sum can be used for optimization.
However, when k = j, we need to compare the sizes of the two numbers of the same length. If the previous number is larger than the current number, this situation is invalid, and we should not add it to dp[i][j]. Otherwise, we can add it to dp[i][j]. Here, we can preprocess the "longest common prefix" in O(n^2) time, and then compare the sizes of two numbers of the same length in O(1) time.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the string num.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with String Comparison | Time Complexity: O(n^2) |
| Recursive Approach with Memoization | Time Complexity: O(n^2) |
| Dynamic Programming + Prefix Sum | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n^3) | O(n^2) | Useful for understanding the partition logic and constraints before optimizing. |
| Dynamic Programming with LCP String Comparison | O(n^2) | O(n^2) | Best choice for large inputs; avoids repeated substring comparisons using precomputed LCP. |
Video Solution
LeetCode 1977. Number of Ways to Separate Numbers • Happy Coding • 3,721 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Number of Ways to Separate Numbers easy or hard?
Number of Ways to Separate Numbers Python/Java solution
How to solve Number of Ways to Separate Numbers in O(n^2)?
What is the best approach for Number of Ways to Separate Numbers?
Is Number of Ways to Separate Numbers asked at Google/Amazon/Meta?
What data structure is used in Number of Ways to Separate Numbers?
What is the time complexity of Number of Ways to Separate Numbers?
Ready to solve this problem?
Practice Number of Ways to Separate Numbers with our built-in code editor and test cases.
Practice on FleetCode