Splitting a String Into Descending Consecutive Values - Solution & Explanation

Problem Overview: You receive a numeric string and must determine whether it can be split into two or more numbers such that every number is exactly 1 less than the previous one. The values must appear in strictly descending consecutive order and each part must preserve its original digit sequence.

Approach 1: Recursive Backtracking (Time: O(2^n), Space: O(n))

This approach tries every possible split for the first number, then recursively checks whether the remaining substring can form a chain of values decreasing by exactly one. After choosing the first number, each recursive step builds the next number digit by digit and compares it with previous - 1. If the value becomes larger than expected, the branch stops early, which prunes many invalid paths. The recursion continues until the entire string is consumed and at least two numbers were formed. This method naturally fits backtracking problems because you explore candidate partitions and abandon invalid states immediately. The implementation usually converts substrings into integers (or uses incremental numeric construction) and keeps track of the last chosen value.

Approach 2: Iterative Reduction with Queue (Time: O(n^2), Space: O(n))

This strategy simulates the splitting process iteratively. Start by generating possible prefixes for the first number and push them into a queue along with the index where the next number should begin. For each queued state, build the next number character by character while comparing it to previous - 1. If the numbers match the required descending pattern, push the new state back into the queue and continue scanning the string. The queue acts as a frontier of partial sequences still being validated. This avoids deep recursion and can be easier to reason about in iterative environments such as JavaScript or C#. The approach still relies heavily on string scanning and numeric comparison, which is common in string parsing tasks.

Both strategies rely on the same key insight: once the first number is fixed, the rest of the sequence is fully determined because each next value must equal previous - 1. The algorithm only needs to verify whether the remaining digits can construct those exact numbers without skipping digits.

Recommended for interviews: Recursive backtracking is the approach most interviewers expect. It clearly demonstrates control over recursion, pruning, and sequence validation using recursion. The queue-based method is a solid alternative when recursion depth is a concern, but the recursive version communicates the core idea more directly.