1977. Number of Ways to Separate Numbers - Leetcode Solution

Problem Description

You are given a string s consisting of digits ('0'-'9'). Your task is to count the number of ways to split s into one or more non-empty substrings so that:

Each substring does not have leading zeros (unless the substring is exactly "0").
The sequence of substrings, when read as integers, forms a non-decreasing sequence.

Return the total number of such ways, modulo 10^9 + 7.

Key constraints:

Splits must cover the whole string; every digit must be used exactly once.
Each substring must be non-empty and cannot have leading zeros unless it is "0".
Each split must result in a non-decreasing sequence (each number is ≥ the previous one).

Thought Process

At first glance, this problem seems to ask for all ways to partition a string into substrings and check if the sequence is non-decreasing. A brute-force approach would be to try every possible split, convert substrings to integers, and check the sequence order and leading zeros. However, since the string can be long (up to 3500 characters), this would be far too slow.

To optimize, we need to avoid recomputing the same subproblems. This suggests using dynamic programming (DP). We can define a state that represents the number of ways to split the string up to a certain index, given the last substring. We also need to efficiently compare substrings for ordering, which can be done with string comparison or precomputed longest common prefix (LCP) arrays.

The main challenge is efficiently checking the non-decreasing constraint and handling leading zeros. We need to iterate over possible partition points and use DP to avoid redundant work.

Solution Approach

We use dynamic programming to count the number of valid ways to split the string. Here’s how:

Define the DP State:
- Let dp[i] be the number of ways to split the prefix s[0:i] (exclusive of i), such that the last number ends at position i-1.
Transitions:
- For each end index i (from 1 to n), consider all possible start indices j (j < i) for the last number.
- Skip if s[j] is '0' and i-j > 1 (leading zero check).
- Compare the previous substring (s[prev_j:j]) to the current substring (s[j:i]) to ensure non-decreasing order.
- If valid, add dp[j] to dp[i].
Initialization:
- Set dp[0] = 1 (empty string has one way).
Substring Comparison Optimization:
- To compare s[j:i] and s[prev_j:j] efficiently, precompute the Longest Common Prefix (LCP) between all pairs of positions.
- This allows O(1) substring comparison for equality and lexicographic order.
Result:
- The answer is dp[n], where n is the length of s.

Why this works: By building up solutions from smaller prefixes and only considering valid, non-decreasing splits, we avoid redundant checks and ensure efficiency.

Example Walkthrough

Consider s = "327":

Possible splits:
- "3" "2" "7" → 3, 2, 7 (not non-decreasing, since 2 < 3)
- "3" "27" → 3, 27 (non-decreasing, since 27 >= 3)
- "32" "7" → 32, 7 (not non-decreasing, since 7 < 32)
- "327" → 327 (single number, valid)
Valid ways: "3 27" and "327" (2 ways)

The DP will build up as follows:

At position 1: "3" (valid, so dp[1] = 1)
At position 2: "32" (valid), but "2" after "3" is not non-decreasing, so dp[2] = 0
At position 3: "327" (valid), "3 27" (valid), "32 7" (invalid), "3 2 7" (invalid), so dp[3] = 2

Time and Space Complexity

Brute-force approach:

There are O(2^n-1) ways to split a string of length n (too slow for n up to 3500).
Each split requires substring parsing and comparison.

Optimized DP approach:

Let n be the length of s.
We fill a DP table of size O(n²), as for each end index, we may consider up to n previous start indices.
LCP precomputation is O(n²).
Each DP transition is O(1) with LCP, so total time is O(n²).
Space is O(n²) for LCP and O(n) for DP.

This is efficient enough for the given constraints.

Summary

We tackled the problem of counting valid ways to split a digit string into non-decreasing, non-leading-zero numbers. By recognizing overlapping subproblems, we used dynamic programming and optimized substring comparison with LCP arrays. This reduced the exponential brute-force search to an efficient O(n²) solution, enabling us to handle large inputs. The key insight was to structure the problem as a prefix DP and carefully handle substring comparisons and leading zero rules.

Code Implementation

MOD = 10**9 + 7

class Solution:
    def numberOfCombinations(self, s: str) -> int:
        n = len(s)
        if s[0] == '0':
            return 0

        # Precompute LCP (Longest Common Prefix)
        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 s[i] == s[j]:
                    lcp[i][j] = lcp[i + 1][j + 1] + 1

        # dp[i][k]: number of ways to split s[0:i] with last part of length k
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for k in range(1, n + 1):
            if s[0] != '0':
                dp[k][k] = 1

        for i in range(1, n + 1):
            for k in range(1, i + 1):
                j = i - k
                if s[j] == '0':
                    continue
                # Add all ways for previous lengths <= k
                if j == 0:
                    dp[i][k] = 1
                    continue
                # Compare s[j-k:j] and s[j:i]
                if j - k >= 0:
                    prev = j - k
                    cmp = 0
                    l = lcp[prev][j]
                    if l >= k or (l < k and s[prev + l] <= s[j + l]):
                        cmp = 1
                    if cmp:
                        dp[i][k] = (dp[i][k] + dp[j][k]) % MOD
                # Add all ways for shorter previous length
                dp[i][k] = (dp[i][k] + sum(dp[j][1:k])) % MOD

        return sum(dp[n][1:]) % MOD

class Solution {
public:
    int numberOfCombinations(string s) {
        int n = s.size();
        const int MOD = 1e9 + 7;
        if (s[0] == '0') return 0;

        // Precompute LCP
        vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (s[i] == s[j]) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }

        // dp[i][k]: number of ways to split s[0:i] with last part of length k
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int k = 1; k <= n; ++k) {
            if (s[0] != '0') {
                dp[k][k] = 1;
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= i; ++k) {
                int j = i - k;
                if (s[j] == '0') continue;
                if (j == 0) {
                    dp[i][k] = 1;
                    continue;
                }
                if (j - k >= 0) {
                    int prev = j - k;
                    int l = lcp[prev][j];
                    if (l >= k || (l < k && s[prev + l] <= s[j + l])) {
                        dp[i][k] = (dp[i][k] + dp[j][k]) % MOD;
                    }
                }
                int sum = 0;
                for (int len = 1; len < k; ++len) {
                    sum = (sum + dp[j][len]) % MOD;
                }
                dp[i][k] = (dp[i][k] + sum) % MOD;
            }
        }

        int res = 0;
        for (int k = 1; k <= n; ++k) res = (res + dp[n][k]) % MOD;
        return res;
    }
};

class Solution {
    public int numberOfCombinations(String s) {
        int n = s.length();
        int MOD = 1000000007;
        if (s.charAt(0) == '0') return 0;

        // Precompute LCP
        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 (s.charAt(i) == s.charAt(j)) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }

        // dp[i][k]: number of ways to split s[0:i] with last part of length k
        int[][] dp = new int[n + 1][n + 1];
        for (int k = 1; k <= n; ++k) {
            if (s.charAt(0) != '0') {
                dp[k][k] = 1;
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= i; ++k) {
                int j = i - k;
                if (s.charAt(j) == '0') continue;
                if (j == 0) {
                    dp[i][k] = 1;
                    continue;
                }
                if (j - k >= 0) {
                    int prev = j - k;
                    int l = lcp[prev][j];
                    if (l >= k || (l < k && s.charAt(prev + l) <= s.charAt(j + l))) {
                        dp[i][k] = (dp[i][k] + dp[j][k]) % MOD;
                    }
                }
                int sum = 0;
                for (int len = 1; len < k; ++len) {
                    sum = (sum + dp[j][len]) % MOD;
                }
                dp[i][k] = (dp[i][k] + sum) % MOD;
            }
        }

        int res = 0;
        for (int k = 1; k <= n; ++k) res = (res + dp[n][k]) % MOD;
        return res;
    }
}

var numberOfCombinations = function(s) {
    const n = s.length;
    const MOD = 1e9 + 7;
    if (s[0] === '0') return 0;

    // Precompute LCP
    const lcp = Array.from({length: n+1}, () => Array(n+1).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = n - 1; j >= 0; --j) {
            if (s[i] === s[j]) {
                lcp[i][j] = lcp[i + 1][j + 1] + 1;
            }
        }
    }

    // dp[i][k]: number of ways to split s[0:i] with last part of length k
    const dp = Array.from({length: n+1}, () => Array(n+1).fill(0));
    for (let k = 1; k <= n; ++k) {
        if (s[0] !== '0') {
            dp[k][k] = 1;
        }
    }

    for (let i = 1; i <= n; ++i) {
        for (let k = 1; k <= i; ++k) {
            let j = i - k;
            if (s[j] === '0') continue;
            if (j === 0) {
                dp[i][k] = 1;
                continue;
            }
            if (j - k >= 0) {
                let prev = j - k;
                let l = lcp[prev][j];
                if (l >= k || (l < k && s[prev + l] <= s[j + l])) {
                    dp[i][k] = (dp[i][k] + dp[j][k]) % MOD;
                }
            }
            let sum = 0;
            for (let len = 1; len < k; ++len) {
                sum = (sum + dp[j][len]) % MOD;
            }
            dp[i][k] = (dp[i][k] + sum) % MOD;
        }
    }

    let res = 0;
    for (let k = 1; k <= n; ++k) res = (res + dp[n][k]) % MOD;
    return res;
};

AlgoMap.io

Want Help Cracking FAANG?