We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Separate Numbers

Number: 2091

Difficulty: Hard

Paid? No

Companies: Microsoft, Walmart Labs

Problem Description

You are given a string of digits representing many positive integers written without commas. The original list of integers is non-decreasing and every integer is written without any leading zeros. Your task is to count the number of possible ways to reinsert commas into the string, so that the resulting list of integers is non-decreasing and every number is positive (i.e. has no leading zero). Because the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • The original integers are required to be in non-decreasing order.
  • No number (apart from the trivial "0" case, which is not allowed) may have a leading zero. This prohibits any partition that creates such numbers.
  • A dynamic programming (DP) approach is used where dp[i] represents the number of valid partitions for the prefix ending at index i.
  • To efficiently compare two numbers (which are represented as substrings) without converting to integers, precompute a longest common prefix (LCP) array.
  • The LCP array helps quickly determine, for two equal‑length substrings, which one is lexicographically smaller (a proxy for numeric comparison).
  • The solution uses a double‑loop DP with an O(n^2) preprocessing step for LCP; n is the length of the input string.

Space and Time Complexity

Time Complexity: O(n^2) – n up to 3500 due to the nested loops and precomputation of the LCP array. Space Complexity: O(n^2) – used for both the DP array (O(n)) and the LCP table (O(n^2)).

Solution

We solve the problem using dynamic programming by letting dp[i] denote the number of valid ways to partition the substring num[0…i-1]. The main idea is to consider every possible partition ending at position i. For a valid partition, the current number must not start with a ‘0’ and, if there is a previous number, it must be less than or equal to the current number. Since the numbers can be very large, we cannot convert the substrings to integers and compare directly. Instead, we precompute an LCP (longest common prefix) table on the string which lets us compare two substrings in O(1) time by first determining how many digits they share in common.

For every possible ending position i, we iterate over all possible starting positions j for the last number. When j is less than the length of the candidate segment (i − j), it means the current segment is the first number and is automatically valid (provided it does not start with ‘0’). Otherwise, we compare the number immediately preceding the current candidate (of the same length) with the candidate. If the previous number is less than or equal to the candidate (either they are equal as determined by the LCP or the first differing digit of the previous number is less than that of the candidate), then this partition is valid and we add dp[j] to dp[i]. Finally, we take the result modulo 10^9 + 7.

We then provide code implementations in Python, JavaScript, C++, and Java.

Code Solutions

# Python solution using DP and LCP precomputation

MOD = 10**9 + 7

def numberOfCombinations(num: str) -> int:
    n = len(num)
    # if the entire string starts with '0', no valid partition is possible.
    if num[0] == '0':
        return 0

    # Precompute LCP: lcp[i][j] = length of longest common prefix of num[i:] and num[j:]
    lcp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if num[i] == num[j]:
                lcp[i][j] = lcp[i + 1][j + 1] + 1
            else:
                lcp[i][j] = 0

    dp = [0] * (n + 1)
    dp[0] = 1  # base case: empty string

    for i in range(1, n + 1):
        if num[i - 1] == '0':  # skip if current segment would start with '0'
            dp[i] = 0
            continue
        # Iterate over all possible split positions
        for j in range(0, i):
            if num[j] == '0':  # can't have a number with leading zero
                continue
            length = i - j  # length of the current number (candidate segment)
            # if j is less than length, then there is no previous number; valid partition.
            if j < length:
                dp[i] = (dp[i] + dp[j]) % MOD
            else:
                # Previous number is num[j - length: j]
                # Compare previous number and current candidate: num[j: i]
                common = lcp[j - length][j]
                # If common >= length then numbers are equal, so valid, 
                # or if the next digit in previous number is less than that in current candidate.
                if common >= length or num[j - length + common] <= num[j + common]:
                    dp[i] = (dp[i] + dp[j]) % MOD
    return dp[n]

# Example usage:
print(numberOfCombinations("327"))  # Expected output: 2
← Back to All Questions