Splitting a String Into Descending Consecutive Values — Medium Problem & Solution

Problem statement

s is a string of digits. Decide whether it can be cut into two or more non-empty consecutive pieces such that, reading each piece as a number, the values strictly decrease by exactly 1 from one piece to the next.

Pieces may have leading zeros — "004" is read as 4. Return true if such a split exists.

Example 1

Input: s = "050043"
Output: true
Explanation: `"05"`, `"004"`, `"3"` read as 5, 4, 3.

Example 2

Input: s = "1234"
Output: false
Explanation: The values would have to decrease, but every split increases.

Example 3

Input: s = "10009998"
Output: true
Explanation: `"100"`, `"099"`, `"98"`.

Constraints

• 1 <= s.length <= 20
• s consists only of digits

How to solve Splitting a String Into Descending Consecutive Values

The first value determines the whole sequence. For each choice of first piece, scan the remainder and match the next expected value; prefixes only grow, so each check stops early.

Approach

1. For every end i of the first piece with i < n - 1, accumulate its value first (stop once it reaches 10^10).
2. dfs(start, prev): if start == n, succeed. Otherwise extend a piece cur from start digit by digit; if cur >= prev, stop; if cur == prev - 1, try dfs(j + 1, cur).
3. Return true when any first piece leads to success.

Why it works

A valid split is fully described by its first piece, and the pruning only discards pieces whose value is already at least prev — adding digits never decreases a value, so those can never equal prev - 1. If the first value has d significant digits, the next one needs at least d - 1, so 2d - 1 <= 20 and the first value is below 10^10, which keeps every quantity inside 64 bits.

Complexity

• Time — O(n^2) per first piece, O(n^3) overall (n ≤ 20)
• Space — O(n) recursion depth

Pitfalls

• At least two pieces are required: the whole string on its own does not count.
• Leading zeros are allowed, so "0090089"-style pieces are legal; do not reject them.
• Parsing a 20-digit piece into a 64-bit integer overflows — prune by value before it gets that large.

Reference solution

Python

def splitString(s: str) -> bool:
    n = len(s)
    limit = 10 ** 10

    def dfs(start, prev):
        if start == n:
            return True
        cur = 0
        for j in range(start, n):
            cur = cur * 10 + ord(s[j]) - 48
            if cur >= prev:
                break
            if cur == prev - 1 and dfs(j + 1, cur):
                return True
        return False

    first = 0
    for i in range(n - 1):
        first = first * 10 + ord(s[i]) - 48
        if first >= limit:
            break
        if dfs(i + 1, first):
            return True
    return False

JavaScript

var splitString = function(s) {
    var n = s.length;
    var LIMIT = 10000000000;
    var dfs = function(start, prev) {
        if (start === n) return true;
        var cur = 0;
        for (var j = start; j < n; j++) {
            cur = cur * 10 + (s.charCodeAt(j) - 48);
            if (cur >= prev) break;
            if (cur === prev - 1 && dfs(j + 1, cur)) return true;
        }
        return false;
    };
    var first = 0;
    for (var i = 0; i < n - 1; i++) {
        first = first * 10 + (s.charCodeAt(i) - 48);
        if (first >= LIMIT) break;
        if (dfs(i + 1, first)) return true;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Ambiguous Coordinates Medium
• Generate Binary Strings Without Adjacent Zeros Medium
• Letter Case Permutation Medium
• Lexicographically Smallest Equivalent String Medium
• Extra Characters in a String Medium
• Minimum Cost to Make All Characters Equal Medium