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#
Example 1#
1
2
3
Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.
Example 2#
1
2
3
4
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#
1
2
3
Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.
Solution#
Method 1 - Backtracking with Pruning#
Intuition#
We want to split the string into two or more substrings such that their numerical values form a strictly descending sequence with each adjacent difference equal to 1. Backtracking allows us to try all possible splits, pruning paths that cannot possibly satisfy the condition.
Approach#
Start from the first character and try every possible split for the first number.
For each split, recursively try to split the rest of the string such that each next number is exactly 1 less than the previous.
Track the previous number and the count of splits. If we reach the end of the string and have at least two numbers, return true.
Prune paths early if the difference is not 1.
Complexity#
⏰ Time complexity: O(n^2) — For each starting index, we try all possible splits, and each recursive call advances the index.
🧺 Space complexity: O(n) — The recursion stack can go up to the length of the string.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public :
bool splitString(string s) {
return backtrack (s, 0 , - 1 , 0 );
}
private :
bool backtrack(const string& s, int idx, long long prev, int count) {
if (idx == s.size()) return count >= 2 ;
long long curr = 0 ;
for (int i = idx; i < s.size(); ++ i) {
curr = curr * 10 + (s[i] - '0' );
if (prev == - 1 || prev - curr == 1 ) {
if (backtrack(s, i + 1 , curr, count + 1 )) return true;
}
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type Solution struct {}
func splitString (s string ) bool {
var backtrack func (idx int , prev int64 , count int ) bool
backtrack = func (idx int , prev int64 , count int ) bool {
if idx == len(s ) {
return count >= 2
}
var curr int64 = 0
for i := idx ; i < len(s ); i ++ {
curr = curr * 10 + int64(s [i ]- '0' )
if prev == - 1 || prev - curr == 1 {
if backtrack (i + 1 , curr , count + 1 ) {
return true
}
}
}
return false
}
return backtrack (0 , - 1 , 0 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean splitString (String s) {
return backtrack(s, 0, - 1, 0);
}
private boolean backtrack (String s, int idx, long prev, int count) {
if (idx == s.length ()) return count >= 2;
long curr = 0;
for (int i = idx; i < s.length (); i++ ) {
curr = curr * 10 + (s.charAt (i) - '0' );
if (prev == - 1 || prev - curr == 1) {
if (backtrack(s, i + 1, curr, count + 1)) return true ;
}
}
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
fun splitString (s: String): Boolean {
fun backtrack (idx: Int, prev: Long, count: Int): Boolean {
if (idx == s.length) return count >= 2
var curr = 0L
for (i in idx until s.length) {
curr = curr * 10 + (s[i] - '0' )
if (prev == -1L || prev - curr == 1L ) {
if (backtrack(i + 1 , curr, count + 1 )) return true
}
}
return false
}
return backtrack(0 , -1L , 0 )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution :
def splitString (self, s: str) -> bool:
def backtrack (idx: int, prev: int, count: int) -> bool:
if idx == len(s):
return count >= 2
curr = 0
for i in range(idx, len(s)):
curr = curr * 10 + int(s[i])
if prev == - 1 or prev - curr == 1 :
if backtrack(i + 1 , curr, count + 1 ):
return True
return False
return backtrack(0 , - 1 , 0 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
pub fn split_string (s: String) -> bool {
fn backtrack (s: & str , idx: usize , prev: i64 , count: usize ) -> bool {
if idx == s.len() {
return count >= 2 ;
}
let mut curr: i64 = 0 ;
for i in idx.. s.len() {
curr = curr * 10 + (s.as_bytes()[i] - b '0' ) as i64 ;
if prev == - 1 || prev - curr == 1 {
if backtrack(s, i + 1 , curr, count + 1 ) {
return true ;
}
}
}
false
}
backtrack(& s, 0 , - 1 , 0 )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
splitString (s : string ): boolean {
function backtrack (idx : number , prev : number , count : number ): boolean {
if (idx === s .length ) return count >= 2 ;
let curr = 0 ;
for (let i = idx ; i < s .length ; i ++ ) {
curr = curr * 10 + Number(s [i ]);
if (prev === - 1 || prev - curr === 1 ) {
if (backtrack (i + 1 , curr , count + 1 )) return true ;
}
}
return false ;
}
return backtrack (0 , - 1 , 0 );
}
}