Compile Ready
Module 7 · Advanced Backtracking

Splitting a String Into Descending Consecutive Values

MediumProblem 17 of 17 8 min read ~22 min to solve LeetCode
BacktrackingDFSStringNumber ParsingPruning
Asked atGoogleAmazonMicrosoftMeta

Problem Statement

Given a digit string s, determine whether it can be split into two or more non-empty substrings such that the numeric values are strictly descending by exactly one from left to right. Substrings may contain leading zeroes, so 004 represents the value 4.

Input

A digit string s.

Output

A boolean indicating whether s can be partitioned into at least two descending consecutive values.

Constraints

  • •1 <= s.length <= 20
  • •s consists only of digits
  • •The split must contain at least two numbers
  • •Leading zeroes are allowed when parsing each number

Examples

Example 1

Input: 
s = 1234
Output: false
Explanation: No split creates values where each next value is exactly one less than the previous value.

Example 2

Input: 
s = 050043
Output: true
Explanation: The split **05 | 004 | 3** gives values **5, 4, 3**.

Example 3

Input: 
s = 10009998
Output: true
Explanation: The split **100 | 099 | 98** gives values **100, 99, 98**.

Learning Objectives

  • Recognise digit-string splitting as a partition backtracking problem.
  • Choose the first number freely, then force every later number to equal the previous value minus one.
  • Allow leading zeroes during parsing while still comparing numeric values.
  • Prune candidates as soon as their parsed value exceeds the required next value.

Intuition

Pattern Recognition + Intuition

This is a partition and cut backtracking problem over a digit string. The first cut is open-ended: it chooses the starting value. After that, the branching collapses into a much tighter rule. If the previous value is x, the next substring must parse to exactly x - 1.

That requirement is the main pruning power. A naive splitter would try every possible sequence of cuts, but here each frame has a known target value. Leading zeroes mean a candidate can start small and become equal later, as 004 becomes 4, so values below the target should keep extending. Once a candidate parses above previous - 1, extending it can only keep it too large, so the rest of that loop is impossible.

Common mistakes

  • ×Rejecting substrings with leading zeroes even though this problem allows them.
  • ×Returning true after consuming the whole string with only one piece.
  • ×Checking only that values are decreasing, instead of decreasing by exactly one.
  • ×Breaking when a candidate is below the expected value, which misses cases like **004** becoming 4.

Algorithm Explanation

State

The first DFS layer chooses the initial prefix value. Every later frame carries index, the next digit position; previous, the numeric value of the last chosen substring; and pieces, the number of chosen substrings. The required next value is always previous - 1.

Recursion tree

For s = 050043, choosing first prefix 0 fails because the next required value would be -1 while substrings are non-negative. Choosing 05 gives previous value 5, so the next value must be 4. At index 2, candidate 0 parses to 0 and is too small, so extend. Candidate 00 is still 0, so extend. Candidate 004 parses to 4 and is chosen. Now the required value is 3, and the final substring 3 consumes the string with three pieces.

Pruning

Use long parsing because prefixes can exceed integer range. If previous - 1 is negative and digits remain, the branch cannot continue. At a frame, extend the candidate substring while its value is below the expected value. If it equals the expected value, recurse. If it exceeds the expected value, break because adding more digits cannot bring the numeric value back down. Parse overflow also means the candidate is too large for any useful comparison, so that loop can stop.

Algorithm

  1. Try every non-empty proper prefix as the first number so at least one digit remains for another piece.
  2. Parse the prefix as a long and start DFS at the next index with pieces = 1.
  3. In DFS, return true only when the whole string is consumed and at least two pieces were chosen.
  4. Compute expected = previous - 1. If it is negative, return false unless the string was already consumed.
  5. Extend the next substring one digit at a time and parse its value.
  6. Continue extending while the value is less than expected.
  7. Recurse only when the value equals expected.
  8. Break the loop when the value exceeds expected or parsing overflows.

Solutions

Solution: DFS with required next value

Choose the first number as a prefix. After that, every recursive frame knows the only acceptable numeric value for the next piece: previous - 1. The search tries longer substrings until it reaches that value, exceeds it, or runs out of digits.

Step-by-step

  1. Iterate over all first prefixes that leave at least one digit for a second number.
  2. Parse the first prefix with Long.parseLong and call DFS.
  3. If DFS reaches the end, accept only when at least two pieces were selected.
  4. For the next piece, compute the required value previous - 1.
  5. Grow the candidate substring from the current index. Values below the requirement keep extending, equality recurses, and values above the requirement stop the loop.
  6. Return true immediately when any branch consumes the full string correctly.
Time

O(n^3)

Space

O(n)

There are O(n^2) candidate substrings across all first-prefix attempts, and parsing substrings can cost O(n). The recursion depth is at most n.

Java implementation

Loading…

Dry Run

Sample input

s = 050043. The successful split is found by choosing a first prefix whose value is 5, then requiring 4 and 3.

stepindexpreviouscandidate substringparsed valueaction
10none00first prefix leads to expected -1, branch fails
20none055choose first value, next must be 4
32500below 4, extend
425000below 4, extend
5250044matches expected, recurse
65433matches expected and consumes string

The split 05 | 004 | 3 succeeds with values 5, 4, 3. The important detail is that leading zeroes are allowed, so candidates smaller than the expected value must be extended rather than rejected.

Interview Tips

State the turning point clearly: after the first number, this is no longer arbitrary partitioning because every next value is forced. Mention leading zeroes before coding, since this problem differs from many digit-partition questions. The safe pruning rule is one-sided: values above the expected next value can stop, but values below it may become equal by appending more digits.

Likely follow-ups

  • How would you return one valid split instead of only a boolean?
  • How would the algorithm change if leading zeroes were forbidden?
  • How would you check ascending consecutive values instead?
  • How would you avoid substring allocation by parsing incrementally?

Similar Problems

Expression Add Operators
HardAlso explores digit-string partitions while carrying numeric state.
Restore IP Addresses
MediumA digit-string splitting problem with strong validity bounds.
Palindrome Partitioning
MediumThe same cut-and-recurse pattern with a different validity predicate.
Split Array into Fibonacci Sequence
MediumAnother numeric string split where previous values force the next value.
Additive Number
MediumUses two previous numeric pieces to constrain the next substring.

Key Takeaways

  • The first number is flexible; every later number is forced to be **previous - 1**.
  • Leading zeroes are allowed, so small candidates may need to keep growing.
  • Break only when a parsed candidate exceeds the required next value or overflows.
  • A valid answer must consume the whole string and contain at least two pieces.
Reusable template: For constrained string splitting, choose the first cut, carry the required next numeric value, extend candidates until they match or exceed it, and accept only full consumption with enough pieces.