LeetCode 1849 - Splitting a String Into Descending Consecutive Values

The problem gives us a numeric string s and asks whether it can be split into at least two non-empty substrings such that their integer values form a strictly descending sequence where every adjacent pair differs by exactly 1.

leetcodemediumstringbacktrackingenumeration

LeetCode Problem 1849

Difficulty: 🟡 Medium
Topics: String, Backtracking, Enumeration

Solution

Problem Understanding

The problem gives us a numeric string s and asks whether it can be split into at least two non-empty substrings such that their integer values form a strictly descending sequence where every adjacent pair differs by exactly 1.

The important detail is that we compare the numerical values of the substrings, not the literal substring text. This means leading zeros are allowed. For example, "05" is interpreted as the integer 5, and "004" is interpreted as 4.

We must determine whether there exists at least one valid partitioning of the string. We are free to choose substring boundaries however we want, as long as:

  1. Every substring is non-empty.
  2. The sequence of numbers is strictly descending.
  3. Each adjacent pair differs by exactly 1.
  4. There are at least two substrings.

For example:

  • "050043" can become ["05", "004", "3"], which corresponds to [5, 4, 3].
  • "1234" cannot be split into a descending consecutive sequence.

The input size is very small, since s.length <= 20. This constraint is extremely important because it tells us exponential exploration is acceptable. In larger input sizes, trying all substring splits would be impossible, but with only 20 characters we can safely use backtracking or DFS.

There are several important edge cases:

  • Strings with leading zeros, such as "0090089".
  • Strings that can only form increasing sequences, such as "001".
  • Very short strings like "1", which cannot be split into at least two parts.
  • Large numeric substrings that exceed 32-bit integer limits. Since the length can be up to 20 digits, we should use arbitrary precision integers in Python and int64 in Go.
  • Cases where multiple partition attempts fail before one succeeds.

Approaches

Brute Force Approach

A brute force solution would generate every possible way to split the string into substrings. For a string of length n, there are 2^(n-1) possible partition patterns because every gap between characters can either contain a split or not.

For each partition configuration, we would:

  1. Convert every substring into an integer.
  2. Check whether the sequence is strictly descending.
  3. Verify every adjacent difference equals 1.

This approach is correct because it examines all possible splits, so if a valid partition exists, it will eventually find it.

However, it is inefficient because every partition must be explicitly constructed and validated. Even though n <= 20 makes it technically feasible, we can do better by pruning invalid paths early.

Optimal Approach, Backtracking with Early Pruning

The key observation is that once we choose the first number, every future number becomes completely determined. If the previous value is x, then the next value must be exactly x - 1.

This means we do not need to generate arbitrary partitions after the first choice. Instead, we can:

  1. Try every possible first substring.
  2. Recursively attempt to match the next required value.
  3. Stop immediately when a substring does not match the expected number.

This drastically reduces unnecessary exploration because invalid branches terminate early.

Since the string length is only 20, recursive backtracking is both simple and efficient enough.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates every partition and validates afterward
Optimal O(2^n) O(n) Backtracking with pruning based on expected next value

Algorithm Walkthrough

Step 1: Choose the first number

We iterate over every possible prefix of the string as the first number.

For example, if s = "050043":

  • First number could be "0"
  • Or "05"
  • Or "050"
  • And so on

We stop before the last character because we need at least two substrings.

Step 2: Start recursive backtracking

Once the first value is chosen, we recursively search for the next substring whose value equals:

previous_value - 1

If the previous value is 5, then the next substring must evaluate to 4.

Step 3: Build the next number incrementally

At each recursive call, we expand the next substring one digit at a time.

For example:

s = "0043"

Possible substrings are:

  • "0" → 0
  • "00" → 0
  • "004" → 4

We continuously build the integer value and compare it to the expected target.

Step 4: Recurse when a match is found

If a substring value equals the expected next value:

  • We recursively continue from the remaining suffix.
  • The matched value becomes the new previous value.

Step 5: Return success when entire string is consumed

If we reach the end of the string successfully, then we found a valid split.

Step 6: Backtrack on failure

If no substring produces the required next value, we return False and try another partition.

Why it works

The algorithm works because every recursive state maintains a strict invariant:

The previously chosen numbers already form a valid descending consecutive sequence.

At each step, we only accept a substring if its value equals exactly previous - 1. Therefore, every recursive extension preserves validity. Since we explore all possible first numbers and all possible matching continuations, the algorithm will find a valid split if one exists.

Python Solution

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)

        def dfs(index: int, previous: int) -> bool:
            if index == n:
                return True

            current = 0

            for end in range(index, n):
                current = current * 10 + int(s[end])

                if current == previous - 1:
                    if dfs(end + 1, current):
                        return True

                if current >= previous:
                    break

            return False

        first = 0

        for i in range(n - 1):
            first = first * 10 + int(s[i])

            if dfs(i + 1, first):
                return True

        return False

The implementation begins by trying every possible prefix as the first number. The variable first is built incrementally to avoid repeated substring conversions.

The recursive dfs function receives two parameters:

  • index, the current position in the string
  • previous, the value the next number must be smaller than

Inside the DFS, we build the next number digit by digit. If the constructed value equals previous - 1, we recurse deeper.

The pruning condition:

if current >= previous:
    break

is important because numbers only grow as we append more digits. Once the current value becomes too large, no future extension can satisfy the descending condition.

If we consume the entire string successfully, we return True.

Go Solution

package main

func splitString(s string) bool {
	n := len(s)

	var dfs func(index int, previous int64) bool

	dfs = func(index int, previous int64) bool {
		if index == n {
			return true
		}

		var current int64 = 0

		for end := index; end < n; end++ {
			current = current*10 + int64(s[end]-'0')

			if current == previous-1 {
				if dfs(end+1, current) {
					return true
				}
			}

			if current >= previous {
				break
			}
		}

		return false
	}

	var first int64 = 0

	for i := 0; i < n-1; i++ {
		first = first*10 + int64(s[i]-'0')

		if dfs(i+1, first) {
			return true
		}
	}

	return false
}

The Go implementation follows the same recursive structure as the Python version.

One important difference is numeric handling. Python integers automatically support arbitrary precision, but Go integers are fixed size. Since the maximum string length is 20, int64 is sufficient for the problem constraints.

Go also requires explicitly declaring the recursive function variable before assigning the function body.

Worked Examples

Example 1

Input: "1234"

Try first number "1":

Remaining Expected Candidate Result
"234" 0 2 Too large

Try first number "12":

Remaining Expected Candidate Result
"34" 11 3 Too small
"34" 11 34 Too large

Try first number "123":

Remaining Expected Candidate Result
"4" 122 4 No match

No valid split exists.

Result:

False

Example 2

Input: "050043"

Choose first substring "05":

Value = 5

Now search for 4.

Remaining Candidate Value Match
"0043" "0" 0 No
"0043" "00" 0 No
"0043" "004" 4 Yes

Now search for 3.

Remaining Candidate Value Match
"3" "3" 3 Yes

Entire string consumed successfully.

Result:

True

Example 3

Input: "9080701"

Try first substring "90":

Expected next value is 89.

Possible next substrings:

Candidate Value
"8" 8
"80" 80
"807" 807

None equal 89.

All other starting choices also fail.

Result:

False

Complexity Analysis

Measure Complexity Explanation
Time O(2^n) In the worst case we explore many substring partition possibilities
Space O(n) Recursive call stack depth is at most the string length

The recursion depth is bounded by n, since every recursive step consumes at least one character. Although the theoretical number of recursive states is exponential, the small constraint n <= 20 makes this practical.

Test Cases

solution = Solution()

assert solution.splitString("1234") == False  # no descending consecutive split
assert solution.splitString("050043") == True  # leading zeros with valid sequence
assert solution.splitString("9080701") == False  # impossible sequence
assert solution.splitString("10009998") == True  # 100,99,98
assert solution.splitString("0090089") == True  # 90,89 with leading zeros
assert solution.splitString("001") == False  # cannot form descending sequence
assert solution.splitString("10") == True  # 1,0
assert solution.splitString("1") == False  # must split into at least two parts
assert solution.splitString("54321") == True  # single digit descending chain
assert solution.splitString("0500403") == False  # breaks sequence
assert solution.splitString("200199198") == True  # 200,199,198
assert solution.splitString("100000099999") == True  # large values
assert solution.splitString("111") == False  # equal numbers not allowed
assert solution.splitString("3210") == True  # descending by one
assert solution.splitString("7654321") == True  # long descending chain
Test Why
"1234" Verifies impossible increasing sequence
"050043" Validates leading zero handling
"9080701" Ensures invalid partitions are rejected
"10009998" Tests multi-digit descending sequence
"0090089" Confirms leading zeros convert correctly
"001" Verifies non-descending values fail
"10" Smallest valid input
"1" Cannot split into two parts
"54321" Tests repeated recursive matching
"0500403" Sequence eventually breaks
"200199198" Larger consecutive values
"100000099999" Large numeric parsing
"111" Equal adjacent values invalid
"3210" Consecutive single digits
"7654321" Deep recursion path

Edge Cases

Leading zeros in substrings

A common source of bugs is treating substrings lexicographically instead of numerically. For example, "004" should be interpreted as integer 4, not as a distinct value. The implementation handles this correctly because every substring is converted numerically during construction.

Very short strings

Strings of length 1 cannot produce at least two substrings. A careless implementation might incorrectly return True if the DFS reaches the end immediately. The solution avoids this by ensuring the initial loop only selects the first number up to n - 1, guaranteeing at least one remaining substring.

Large numeric values

The string can contain up to 20 digits, which may overflow standard 32-bit integers. Python naturally supports arbitrarily large integers, while the Go solution explicitly uses int64. This ensures comparisons remain correct even for large substrings.

Paths that partially match before failing

Some inputs may appear valid initially but fail later. For example, "1098" works as 10,9,8, but "1097" fails after the first step. The recursive backtracking correctly explores deeper states and backtracks when later conditions fail.