Formatted question description: https://leetcode.ca/all/1849.html

# 1849. Splitting a String Into Descending Consecutive Values

## Level

Medium

## Description

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.

**Example 4:**

**Input:** s = “10009998”

**Output:** true

**Explanation:** s can be split into [“100”, “099”, “98”] with numerical values [100,99,98].

The values are in descending order with adjacent values differing by 1.

**Constraints:**

`1 <= s.length <= 20`

`s`

only consists of digits.

## Solution

Use backtrack to find a way to split the string. If the current substring represents a numerical value that is less than the previous numerical value by 1, then split the current substring. If the end of the string is reached and there are at least two parts, return `true`

. If no such a way is found, return `false`

.

```
class Solution {
public boolean splitString(String s) {
int length = s.length();
long firstNum = 0;
for (int i = 0; i < length - 1; i++) {
firstNum = firstNum * 10 + (s.charAt(i) - '0');
boolean flag = backtrack(s, 1, firstNum, i + 1);
if (flag)
return true;
}
return false;
}
public boolean backtrack(String s, int count, long prev, int start) {
int length = s.length();
if (start == length)
return count > 1;
for (int i = start + 1; i <= length; i++) {
String currStr = s.substring(start, i);
long curr = Long.parseLong(currStr);
if (curr >= prev)
break;
if (prev - curr == 1) {
boolean flag = backtrack(s, count + 1, curr, i);
if (flag)
return true;
}
}
return false;
}
}
```