Scale Engineer

Number of Ways to Separate Numbers

Hard
#1802Time: O(2^n * n)Space: O(n)1 company
Patterns
Dynamic Programming
Data structures
StringSuffix Array
Companies
Walmart Labs

Prompt

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 <= 3500
  • num consists of digits '0' through '9'.

Approaches

3 approaches with complexity analysis and trade-offs.

The most intuitive approach is to try all possible partitions of the number string num using recursion (backtracking). We can explore every possible way to split the string and, for each complete partition, check if it satisfies the given conditions: the sequence of numbers is non-decreasing and no number has a leading zero.

Algorithm

  • Define a recursive function backtrack(startIndex, prevNumStr) which returns the number of valid partitions for the suffix num.substring(startIndex) given the previous number was prevNumStr.
  • Base Case: If startIndex reaches the end of the string, a valid partition has been found, so return 1.
  • Recursive Step:
    • Initialize a counter ways = 0.
    • Iterate i from startIndex to the end of the string.
    • Form the currentNumStr from startIndex to i.
    • Validation & Pruning:
      • If currentNumStr has a leading zero (and is not just "0"), it's invalid. Since any longer string starting at startIndex will also have a leading zero, we can break the loop.
      • Compare currentNumStr with prevNumStr. If currentNumStr is smaller, this path is invalid, so we continue to the next iteration to form a larger number.
      • The comparison is done first by length, then lexicographically if lengths are equal.
    • If currentNumStr is valid, recursively call backtrack(i + 1, currentNumStr) and add the result to ways.
  • The initial call is backtrack(0, "").

Walkthrough

We define a recursive helper function that explores all possible splits. This function takes the current starting index and the string representation of the previous number as parameters. It iterates through all possible endpoints for the current number, forming a substring. For each substring, it checks two conditions: validity (no leading zeros) and the non-decreasing property (the current number must be greater than or equal to the previous one). If the conditions are met, it makes a recursive call for the rest of the string. The sum of the results from these recursive calls gives the total number of ways for the current state. This method explores the entire search space of partitions, which grows exponentially with the length of the input string.

class Solution {    int n;    String num;    int MOD = 1_000_000_007;     public int numberOfCombinations(String num) {        this.num = num;        this.n = num.length();        if (num.charAt(0) == '0') {            return 0;        }        // Using a 2D array for memoization would turn this into a DP solution.        // Without it, it's pure backtracking.        return backtrack(0, "");    }     private int backtrack(int startIndex, String prevNumStr) {        if (startIndex == n) {            return 1;        }         long totalWays = 0;        for (int i = startIndex; i < n; i++) {            String currentNumStr = num.substring(startIndex, i + 1);             if (currentNumStr.length() > 1 && currentNumStr.charAt(0) == '0') {                break; // Pruning            }             if (!prevNumStr.isEmpty()) {                if (currentNumStr.length() < prevNumStr.length()) {                    continue; // Pruning                }                if (currentNumStr.length() == prevNumStr.length() && currentNumStr.compareTo(prevNumStr) < 0) {                    continue; // Pruning                }            }             totalWays = (totalWays + backtrack(i + 1, currentNumStr)) % MOD;        }        return (int) totalWays;    }}

Complexity

Time

O(2^n * n)

Space

O(n)

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for very small inputs.

Cons

  • Extremely inefficient with a time complexity that is exponential.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

  • Recalculates solutions for the same subproblems repeatedly.

Solutions

class Solution {private  static final int MOD = (int)1 e9 + 7;public  int numberOfCombinations(String num) {    int n = num.length();    int[][] lcp = new int[n + 1][n + 1];    for (int i = n - 1; i >= 0; --i) {      for (int j = n - 1; j >= 0; --j) {        if (num.charAt(i) == num.charAt(j)) {          lcp[i][j] = 1 + lcp[i + 1][j + 1];        }      }    }    int[][] dp = new int[n + 1][n + 1];    dp[0][0] = 1;    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= i; ++j) {        int v = 0;        if (num.charAt(i - j) != '0') {          if (i - j - j >= 0) {            int x = lcp[i - j][i - j - j];            if (x >= j || num.charAt(i - j + x) >= num.charAt(i - j - j + x)) {              v = dp[i - j][j];            }          }          if (v == 0) {            v = dp[i - j][Math.min(j - 1, i - j)];          }        }        dp[i][j] = (dp[i][j - 1] + v) % MOD;      }    }    return dp[n][n];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem