> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Splitting a String Into Descending

> Tested Python solution for LeetCode 1849 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 1849, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking), [Enumeration](/catalog/topics/enumeration). [View on LeetCode](https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1849   # by problem number
lcpy gen -s splitting_a_string_into_descending_consecutive_values   # by problem name
```

## Problem

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.

### Examples

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

```
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.
```

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

### Constraints

* 1 \<= s.length \<= 20
* s only consists of digits.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/splitting_a_string_into_descending_consecutive_values/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/splitting_a_string_into_descending_consecutive_values/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from functools import cache


class Solution:
    # Time: O(n^2) states explored via DFS over cut positions
    # Space: O(n) for recursion depth and memoization
    def split_string(self, s: str) -> bool:
        n = len(s)

        @cache
        def dfs(i: int, prev: int) -> bool:
            if i == n:
                return True
            for j in range(i + 1, n + 1):
                val = int(s[i:j])
                if prev - val == 1 and dfs(j, val):
                    return True
            return False

        # The first piece must leave at least one character for a second piece.
        return any(dfs(j, int(s[:j])) for j in range(1, n))
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) states explored via DFS over cut positions | O(n) for recursion depth and memoization |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.