Splitting a String Into Descending Consecutive Values
Problem
You are given a string s made up only of digits. Decide whether you can cut it into two or more contiguous pieces so that, reading left to right, the numeric value of each piece is exactly one less than the value of the piece before it. Leading zeros are allowed inside a piece (so "004" counts as the number 4). Return true if at least one such split exists, otherwise false.
s = "050043"true"05", "004", "3" giving values 5, 4, 3 — each is one less than the previous.def splitString(s):
n = len(s)
def backtrack(start, prev):
if start == n:
return True
val = 0
for end in range(start, n):
val = val * 10 + int(s[end])
if val == prev - 1 and backtrack(end + 1, val):
return True
if val >= prev:
break
return False
first = 0
for end in range(n - 1):
first = first * 10 + int(s[end])
if backtrack(end + 1, first):
return True
return Falsefunction splitString(s) {
const n = s.length;
function backtrack(start, prev) {
if (start === n) return true;
let val = 0;
for (let end = start; end < n; end++) {
val = val * 10 + (s.charCodeAt(end) - 48);
if (val === prev - 1 && backtrack(end + 1, val)) return true;
if (val >= prev) break;
}
return false;
}
let first = 0;
for (let end = 0; end < n - 1; end++) {
first = first * 10 + (s.charCodeAt(end) - 48);
if (backtrack(end + 1, first)) return true;
}
return false;
}class Solution {
public boolean splitString(String s) {
int n = s.length();
long first = 0;
for (int end = 0; end < n - 1; end++) {
first = first * 10 + (s.charAt(end) - '0');
if (backtrack(s, end + 1, first)) return true;
}
return false;
}
private boolean backtrack(String s, int start, long prev) {
if (start == s.length()) return true;
long val = 0;
for (int end = start; end < s.length(); end++) {
val = val * 10 + (s.charAt(end) - '0');
if (val == prev - 1 && backtrack(s, end + 1, val)) return true;
if (val >= prev) break;
}
return false;
}
}bool backtrack(const string& s, int start, long long prev) {
if (start == (int)s.size()) return true;
long long val = 0;
for (int end = start; end < (int)s.size(); end++) {
val = val * 10 + (s[end] - '0');
if (val == prev - 1 && backtrack(s, end + 1, val)) return true;
if (val >= prev) break;
}
return false;
}
bool splitString(string s) {
int n = s.size();
long long first = 0;
for (int end = 0; end < n - 1; end++) {
first = first * 10 + (s[end] - '0');
if (backtrack(s, end + 1, first)) return true;
}
return false;
}Explanation
The whole string must turn into a chain of numbers like 5, 4, 3 where every number is exactly one smaller than the one before it. We do not know how long the first number should be, so we try every possible length for it and let recursion handle the rest.
Once the first piece is fixed, the rest is forced: the next piece must equal prev − 1. So inside backtrack(start, prev) we grow a number digit by digit from position start. The moment that running value equals prev − 1, we recurse from just after it, asking the same question with the new prev.
If we ever reach the end of the string having consumed everything, every piece lined up correctly and we return true. A handy pruning rule: while building a piece, if its value already grows to prev or larger it can never be prev − 1 by adding more digits, so we stop extending that piece early.
Walking the example "050043": take "05" = 5 as the first number. Now we need 4 — the digits "004" read as 4, perfect. Now we need 3 — the final "3" is exactly 3, and the string is finished, so the answer is true.
Leading zeros are fine because we read each piece as a plain integer, so "004" is just 4. We only commit to a split when the numbers genuinely descend by one, which is what makes the backtracking quickly discard dead ends.