# Splitting a String Into Descending Consecutive Values
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values)
Canonical: https://scaleengineer.com/dsa/problems/splitting-a-string-into-descending-consecutive-values
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## 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.

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

# Approaches
## Unguided Backtracking Search
This approach uses a standard backtracking algorithm to explore all possible partitions of the string. It recursively builds partitions, and only when a full partition of the entire string is formed does it check if the partition satisfies the descending consecutive value condition. It doesn't use the problem's constraints to guide the search process, leading to a lot of unnecessary exploration.
**Time:** O(N * 2^N). The number of partitions of a string of length N is 2^(N-1). For each partition, we do a check that takes O(N) time. This results in an exponential runtime. · **Space:** O(N), where N is the length of the string. This is for the recursion stack depth and the list storing the current partition's numbers.
**Pros:** Simple to understand and implement.; Guaranteed to be correct as it checks every single possibility.
**Cons:** Highly inefficient as it explores the entire search space of `2^(N-1)` partitions.; Performs a lot of redundant computations by exploring paths that could have been identified as invalid much earlier.; Can easily lead to a 'Time Limit Exceeded' error on larger inputs within the given constraints.
### Explanation
The core idea is to generate every single way the string can be split into non-empty parts. This can be achieved with a recursive function that, at each step, decides the length of the next part. When the entire string is partitioned, we then verify if this specific partition meets the problem's criteria.

For example, for `s = "109"`, the backtracking function would explore partitions like `["1", "0", "9"]`, `["1", "09"]`, `["10", "9"]`, etc. For each complete partition, like `["10", "9"]`, we convert them to numbers `[10, 9]` and check if `10 - 9 == 1`. Since it is, we've found a solution.

This method is exhaustive but naive because it doesn't stop exploring a path even if it's clearly not going to work. For instance, after forming the partial partition `["1", "09"]` (values `[1, 9]`), it doesn't stop, even though `1` followed by `9` already violates the descending order rule.

```java
class Solution {
    public boolean splitString(String s) {
        return backtrack(s, 0, new ArrayList<>());
    }

    private boolean backtrack(String s, int index, List<Long> nums) {
        if (index == s.length()) {
            return nums.size() >= 2 && isDescendingConsecutive(nums);
        }

        for (int i = index; i < s.length(); i++) {
            String sub = s.substring(index, i + 1);
            long currentNum = Long.parseLong(sub);
            
            nums.add(currentNum);
            if (backtrack(s, i + 1, nums)) {
                return true;
            }
            nums.remove(nums.size() - 1); // Backtrack
        }
        
        return false;
    }

    private boolean isDescendingConsecutive(List<Long> nums) {
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) - nums.get(i + 1) != 1) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a recursive function, say `backtrack(index, current_partition)`, that explores all possible ways to partition the string.
- The `index` parameter tracks the current position in the string `s`.
- The `current_partition` is a list that stores the numerical values of the substrings in the partition being built.
- The base case for the recursion is when `index` reaches the end of the string. At this point, check if the `current_partition` is a valid split.
- A partition is valid if it contains at least two numbers and follows the descending-by-one rule.
- The recursive step iterates from `index` to the end of the string, creating every possible next substring. For each substring, it's parsed into a number, added to `current_partition`, and a recursive call is made for the rest of the string.
- After the recursive call returns, the last added number is removed (this is the "backtracking" step) to explore other possibilities.
- If any recursive path leads to a valid partition, return `true` immediately.

## Guided Backtracking with Pruning
This is a more intelligent backtracking approach that uses the problem's constraints to guide the search and prune invalid branches early. Instead of generating a full partition and then checking it, this method checks the descending-by-one condition at each step. This allows it to abandon paths that cannot possibly lead to a solution, making it significantly more efficient.
**Time:** The worst-case complexity is still exponential, O(2^N), but it is much faster in practice. The pruning and guided nature of the search eliminate a vast number of branches from the search tree, making its average-case performance significantly better than the unguided approach. · **Space:** O(N), where N is the length of the string. This space is used by the recursion call stack, which can go at most N levels deep.
**Pros:** Significantly more efficient than the naive backtracking approach due to guided search and pruning.; Low space complexity.; Effectively solves the problem within typical time limits for the given constraints.
**Cons:** The logic is more complex to reason about compared to the naive approach.; The worst-case time complexity remains exponential, although such cases are rare in practice.
### Explanation
This optimized approach avoids the inefficiency of the unguided search by incorporating the problem's main constraint directly into the search logic. We start by trying every possible first number. Once a first number `val` is chosen, the rest of the search is constrained: the very next number *must* be `val - 1`.

Our recursive function `dfs(index, prevVal)` doesn't search for any partition; it specifically searches for a partition of `s.substring(index)` that starts with the number `prevVal - 1`.

This is much faster because the search space is drastically reduced. Furthermore, we add a pruning optimization. When we are parsing the next number, if its value already exceeds the target value (`prevVal - 1`), we know that making it longer will only increase its value. Therefore, we can stop searching down that path and backtrack immediately.

```java
class Solution {
    public boolean splitString(String s) {
        // Iterate through all possible lengths for the first number.
        for (int i = 0; i < s.length() - 1; i++) {
            String firstSub = s.substring(0, i + 1);
            long firstNum = Long.parseLong(firstSub);
            if (dfs(s, i + 1, firstNum)) {
                return true;
            }
        }
        return false;
    }

    private boolean dfs(String s, int index, long prevNum) {
        // Base case: we've successfully partitioned the whole string.
        if (index == s.length()) {
            return true;
        }

        // Try to find the next number in the sequence.
        for (int j = index; j < s.length(); j++) {
            String currentSub = s.substring(index, j + 1);
            long currentNum = Long.parseLong(currentSub);

            if (currentNum == prevNum - 1) {
                // Found the next number, recurse for the rest of the string.
                if (dfs(s, j + 1, currentNum)) {
                    return true;
                }
            }
            
            // Pruning: if the current number is already larger than the target,
            // no need to check longer substrings from this point.
            if (currentNum > prevNum - 1) {
                break;
            }
        }

        return false;
    }
}
```
### Algorithm
- The main function iterates through all possible lengths of the *first* number in the sequence. A split must have at least two parts, so the first number cannot be the entire string.
- For each choice of a first number, `firstVal`, a recursive helper function, `dfs(index, prevVal)`, is called to find the rest of the sequence.
- The `dfs` function's goal is to find a number equal to `prevVal - 1` starting at `index`.
- It iterates, forming a `currentVal` from the substring `s.substring(index, j+1)`.
- If `currentVal == prevVal - 1`, a valid next number is found. The function then recursively calls `dfs` for the remainder of the string: `dfs(j + 1, currentVal)`.
- **Pruning:** If at any point `currentVal` becomes greater than the target `prevVal - 1`, we can stop extending the current substring (i.e., break the inner loop). This is because any longer substring will represent an even larger number, so it can't possibly be the target.
- The base case for the recursion is reaching the end of the string (`index == s.length()`), which signifies a successful partition. In this case, it returns `true`.

# Solutions
### Java

```java
class Solution {
private
  String s;
public
  boolean splitString(String s) {
    this.s = s;
    return dfs(0, -1, 0);
  }
private
  boolean dfs(int i, long x, int k) {
    if (i == s.length()) {
      return k > 1;
    }
    long y = 0;
    for (int j = i; j < s.length(); ++j) {
      y = y * 10 + (s.charAt(j) - '0');
      if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool splitString(string s) {
    function<bool(int, long long, int)> dfs = [&](int i, long long x,
                                                  int k) -> bool {
      if (i == s.size()) {
        return k > 1;
      }
      long long y = 0;
      for (int j = i; j < s.size(); ++j) {
        y = y * 10 + (s[j] - '0');
        if (y > 1e10) {
          break;
        }
        if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
          return true;
        }
      }
      return false;
    };
    return dfs(0, -1, 0);
  }
};

```

### Python

```python
class Solution:
    def splitString(self, s: str) -> bool: def dfs(i, x, k): if i == len(s): return k > 1 y = 0 for j in range(i, len(s)): y = y * 10 + int(s[j]) if (x == - 1 or x - y == 1) and dfs(j + 1, y, k + 1): return True return False return dfs(0, - 1, 0)

```