Number of Ways to Separate Numbers - Practice Coding Problems

Number of Ways to Separate Numbers - Problem

You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to separate 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: num = "327"

› Output: 2

💡 Note: Two valid ways: [3, 27] since 3 ≤ 27, and [327] as single number. Cannot use [32, 7] because 32 > 7.

Example 2 — Single Digit

$ Input: num = "9"

› Output: 1

💡 Note: Only one way: [9] as single number.

Example 3 — Leading Zeros

$ Input: num = "094"

› Output: 0

💡 Note: No valid splits because numbers cannot have leading zeros. "094", "09", "04", "0" all have leading zeros.

Constraints

1 ≤ num.length ≤ 3500
num consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits without separators

Process

Find all ways to split into non-decreasing numbers

Output

Count of valid splitting methods

Key Takeaway

🎯 Key Insight: Use dynamic programming to systematically count all valid non-decreasing splits while avoiding leading zeros

Asked in

G Google 15 f Facebook 12

The key insight is to use dynamic programming to count valid ways to split the string into non-decreasing numbers without leading zeros. Best approach uses 2D DP with optimized string comparison via longest common prefix preprocessing. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^n)	O(n)	Try all possible ways to split the string recursively
Dynamic Programming with Memoization	O(n³)	O(n²)	Cache results of subproblems to avoid recomputation
2D Dynamic Programming	O(n³)	O(n²)	Build solution using 2D table with optimized string comparison

Recursive Backtracking — Algorithm Steps

For each position, try all possible number lengths
Check if current number >= previous number
Recursively solve for remaining string
Sum all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at position 0, try different lengths

Split

For each valid split, recurse on remaining string

Count

Sum all valid complete splits

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

#define MOD 1000000007
#define MAXN 3505

int compare(char* num, int start1, int len1, int start2, int len2) {
    if (len1 != len2) return len1 - len2;
    for (int i = 0; i < len1; i++) {
        if (num[start1 + i] != num[start2 + i]) {
            return num[start1 + i] - num[start2 + i];
        }
    }
    return 0;
}

long long backtrack(char* num, int pos, int prevStart, int prevLen, int n) {
    if (pos == n) return 1;
    
    long long result = 0;
    for (int length = 1; length <= n - pos; length++) {
        if (num[pos] == '0' && length > 1) break;
        
        if (prevStart != -1) {
            if (compare(num, pos, length, prevStart, prevLen) < 0) {
                continue;
            }
        }
        
        result = (result + backtrack(num, pos + length, pos, length, n)) % MOD;
    }
    
    return result;
}

int solution(char* num) {
    int n = strlen(num);
    return backtrack(num, 0, -1, 0, n);
}

int main() {
    char num[MAXN];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can start a new number, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to string length

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler