Skip to main content
Talentd

Splitting a String Into Descending Consecutive Values - Solution & Explanation

MediumStringBacktracking12 min read
Practice this problem

Problem Statement

You are given a string s that consists of only digits.

Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.

  • For example, the string s = "0090089" can be split into ["0090", "089"] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
  • Another example, the string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0", "0", "1"]. However all the ways are invalid because they have numerical values [0,1], [0,1], and [0,0,1] respectively, all of which are not in descending order.

Return true if it is possible to split sā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ as described above, or false otherwise.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.

Example 2:

Input: s = "050043"
Output: true
Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.

Example 3:

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.

 

Constraints:

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

Approach Overview

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.

Approach 1: Recursive Backtracking

This approach involves recursively attempting to split the string into valid descendent values using backtracking. For each possible prefix, try finding a valid sequence recursively starting from the remaining string.

The function uses a helper function check to recurse through the string. Initially, we try every prefix of the string for the first number and use recursion to validate if the rest of the string can form a sequence of descending numbers, each 1 less than the previous.

If for any initial prefix, a valid sequence is found until the end, the function returns True.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n^2 * m), where n is the length of s and m is the maximum number length possible.
Space Complexity: O(n), due to the recursive stack.

Try this approach in the editor ā†’

Approach 2: Iterative Reduction with Queue

This approach utilizes a queue to iteratively reduce the problem by exploring valid sequences, without explicitly using the recursion stack.

Instead of utilizing recursion, we maintain a dynamic state in a queue, iterating over subsequent possible splits and validating if they maintain the bubbling property (decrement by 1). By utilizing BigInt, we handle large values efficiently in JavaScript.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n^2 * m), with n being string length, and m maximum partition length (handled by BigInt operations).
Space Complexity: O(n) due to queue size management at each step.

Try this approach in the editor ā†’

Approach 3: DFS

We can start from the first character of the string and try to split it into one or more substrings, then recursively process the remaining part.

Specifically, we design a function dfs(i, x), where i represents the current position being processed, and x represents the last split value. Initially, x = -1, indicating that we have not split out any value yet.

In dfs(i, x), we first calculate the current split value y. If x = -1, or x - y = 1, then we can try to use y as the next value and continue to recursively process the remaining part. If the result of the recursion is true, we have found a valid split method and return true.

After traversing all possible split methods, if no valid split method is found, we return false.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Recursive Backtracking

Time Complexity: O(n^2 * m), where n is the length of s and m is the maximum number length possible.
Space Complexity: O(n), due to the recursive stack.

Iterative Reduction with Queue

Time Complexity: O(n^2 * m), with n being string length, and m maximum partition length (handled by BigInt operations).
Space Complexity: O(n) due to queue size management at each step.

DFSā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive BacktrackingO(2^n)O(n)Best for interviews and typical solutions; clean exploration of all valid splits with pruning
Iterative Reduction with QueueO(n^2)O(n)Useful when avoiding recursion or implementing state exploration iteratively

Video Solution

Splitting a String Into Descending Consecutive Values - Leetcode 1849 - Python ā€¢ NeetCode ā€¢ 22,081 views views

Watch 7 more video solutions ā†’

Frequently Asked Questions

Is Splitting a String Into Descending Consecutive Values easy or hard?
The problem is rated Medium because the core idea is simple but the implementation requires careful handling of numeric construction, recursion termination, and pruning conditions. Managing large numbers and preventing invalid branches adds moderate complexity.
Splitting a String Into Descending Consecutive Values Python/Java solution
Python and Java implementations usually follow the recursive backtracking approach. The algorithm selects a prefix as the first number, then recursively constructs the next number and checks whether it equals previous - 1. If the entire string is consumed while maintaining the descending rule, the function returns true.
How to solve Splitting a String Into Descending Consecutive Values in O(n)?
A strict O(n) solution generally isn't feasible because the algorithm must try multiple possible starting splits. Once the first number is fixed, validation becomes linear, but determining that first split requires exploring several possibilities. Most accepted implementations run in exponential time with pruning or around O(n^2) using iterative state exploration.
What is the best approach for Splitting a String Into Descending Consecutive Values?
Recursive backtracking is the most common approach. You try different prefixes as the first number and recursively check whether the remaining digits can form numbers that decrease by exactly one each time. Pruning occurs when a constructed number becomes larger than the expected value. The overall complexity is roughly O(2^n) in the worst case with O(n) recursion space.
Is Splitting a String Into Descending Consecutive Values asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Amazon and Google because it combines string parsing, recursion, and number construction. Interviewers use it to test backtracking skills and the ability to prune invalid search branches early.
What data structure is used in Splitting a String Into Descending Consecutive Values?
The core solution primarily uses recursion or a queue to track partial states. Backtracking implementations rely on the call stack to explore splits, while iterative versions maintain a queue storing the previous value and the current index in the string.
What is the time complexity of Splitting a String Into Descending Consecutive Values?
The typical backtracking solution runs in O(2^n) time because the algorithm explores many possible partitions of the string. Each recursive branch attempts to build the next numeric value and stops early when it exceeds the expected number. Space complexity is O(n) due to recursion depth and substring construction.

Ready to solve this problem?

Practice Splitting a String Into Descending Consecutive Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring