Splitting a String Into Descending Consecutive Values: Backtracking

LeetCode Splitting a String Into Descending Consecutive Values (problem 1849) gives you a string s consisting only of digits. Your task is to determine whether you can split s into two or more non-empty substrings such that the numerical values of the substrings form a strictly descending sequence where each value is exactly 1 less than the previous one.

For example, the string "0090089" can be split as ["0090", "089"], which gives the values [90, 89]. Since 90 and 89 are consecutive descending values, the answer is true.

Why this problem matters

This problem is a clean exercise in backtracking with a string-splitting twist. Unlike many backtracking problems where you choose from a list of candidates, here you choose a split point in a string. The "candidate" at each step is a prefix of the remaining string, and the constraint is that its numerical value must equal the previous value minus one. This teaches you how to apply the backtracking template to problems where the search space is defined by substrings rather than array elements.

It also forces you to deal with leading zeros. The substring "049" is a valid representation of the number 49. You cannot skip substrings just because they start with zero. This subtle detail trips up many people who try to prune too aggressively.

The key insight

Once you fix the first number, the entire rest of the sequence is determined. If the first number is k, the next number must be k - 1, then k - 2, and so on. So the problem reduces to: try every possible first number (every prefix of the string), then greedily check whether the remaining string can be partitioned into the required descending sequence.

The backtracking structure is simple. At each step you know the exact value you need next. You scan through prefixes of the remaining string looking for one whose numerical value matches. If you find it, recurse on the rest of the string with the next target value. If no prefix matches, backtrack and try a longer first number.

The solution

def splitString(s: str) -> bool:
    def backtrack(index, prev, parts):
        if index == len(s):
            return parts >= 2

        for end in range(index + 1, len(s) + 1):
            val = int(s[index:end])
            if val == prev - 1:
                if backtrack(end, val, parts + 1):
                    return True
            if val > prev - 1 and parts > 0:
                break

        return False

    for end in range(1, len(s)):
        first_val = int(s[:end])
        if backtrack(end, first_val, 1):
            return True

    return False

The outer loop tries every possible first number by taking prefixes of length 1, 2, 3, and so on (stopping before the entire string, since we need at least two parts). For each first number, the backtrack function tries to consume the rest of the string one segment at a time.

Inside backtrack, we know we need prev - 1 as the next value. We try every prefix of the remaining string starting at index. If a prefix equals prev - 1, we recurse with the updated position and the new target. If we reach the end of the string with at least two parts total, we return True.

The pruning on line if val > prev - 1 and parts > 0 is an optimization. Since longer prefixes produce larger numbers, once the current prefix exceeds the target value, no longer prefix will match either, so we can break early. We only apply this when parts > 0 because the first number has no constraint to check against.

Visual walkthrough

Let's trace through the algorithm with s = "050049". The backtracking tries different first numbers and checks whether the rest of the string can form a valid descending sequence.

Notice how the algorithm quickly eliminates invalid first numbers. Starting with "0" fails because the next value would need to be -1. Starting with "05" (value 5) means the next value must be 4, and while "004" matches 4, the leftover "9" does not equal 3. Only when the first number is "050" (value 50) does the remaining "049" match the required 49, completing a valid two-part split.

Complexity analysis

The time complexity is O(n^2) in the worst case, where n is the length of the string. The outer loop tries up to n - 1 starting positions. For each starting position, the recursive function scans through prefixes of the remaining string. In the worst case, each recursive call does O(n) work scanning prefixes, and the recursion depth is bounded by n (since each step consumes at least one character). However, the early termination from the pruning condition and the fact that we know the exact target value at each step mean that in practice the algorithm runs much faster than the worst case.

The space complexity is O(n) for the recursion stack. Each recursive call consumes at least one character, so the maximum depth is n.

The building blocks

1. String to number conversion with leading zeros

Python's int() function handles leading zeros naturally. int("049") returns 49, and int("00007") returns 7. This is important because the problem allows substrings with leading zeros. You do not need any special parsing logic. Just convert the substring to an integer and compare.

In languages like C++ or Java, you need to be more careful. Very long substrings can overflow standard integer types, so you may need to use big integers or add length-based bounds to avoid overflow before it happens.

2. Backtracking with a target value

The standard backtracking template is choose-explore-unchoose. In this problem, the "choose" step is selecting a prefix of the remaining string. The "explore" step is recursing with the rest of the string and the next target value. There is no explicit "unchoose" step because we are not modifying any shared state. The function simply tries different prefix lengths in a loop.

This pattern appears whenever the search space is defined by partitioning a string into segments. You see it in Restore IP Addresses, Palindrome Partitioning, and Additive Number. The only difference between these problems is the constraint each segment must satisfy.

Edge cases

• All identical digits. s = "1111" can be split as ["1", "1", "1", "1"], but these are not strictly descending. However, note that this is not descending consecutive because all values are equal. Return false.
• Single character. s = "5" cannot be split into two or more parts. Return false.
• Leading zeros. s = "050049" should return true. The substrings "050" and "049" are valid representations of 50 and 49.
• Very large numbers. If the string is long, the first number could be enormous. In Python, big integers are handled natively. In other languages, watch for overflow.
• Descending to zero. s = "10" splits as ["1", "0"], giving [1, 0]. These are consecutive descending values (1 - 0 = 1), so return true.
• Two characters. s = "21" splits as ["2", "1"]. Consecutive descending. Return true. But s = "13" gives [1, 3] (ascending) or [13] (only one part). Return false.

From understanding to recall

You understand the backtracking structure and the insight that the first number determines the entire sequence. But can you write this solution from scratch in two minutes during an interview? The tricky details are the loop bounds (stopping one character before the end to ensure at least two parts), the pruning condition (breaking when the prefix exceeds the target), and remembering that int() handles leading zeros.

Spaced repetition turns understanding into automatic recall. You practice writing the outer loop that tries each first number, the recursive function that matches exact target values, and the pruning logic. After a few rounds, the pattern is locked in. You see a string-splitting backtracking problem and the code writes itself.

Related posts

• Restore IP Addresses - Backtracking to split a string into valid segments
• Palindrome Partitioning - Backtracking to split a string where each part satisfies a condition
• Additive Number - Similar string splitting with a numerical relationship between parts

CodeBricks breaks Splitting a String Into Descending Consecutive Values into its core backtracking building block, then drills it independently with spaced repetition. You type the partition-and-validate pattern from scratch until it is automatic. When a string-splitting backtracking problem shows up in your interview, you do not hesitate. You just write it.