Splitting a String Into Descending Consecutive Values
Medium · Backtracking · String · Backtracking
Problem
You are given a string s of digits. Decide whether s can be split into two or more non-empty pieces so that their numeric values, read left to right, are in descending order and each adjacent pair differs by exactly 1.
Pieces may have leading zeros: "0090089" can be split as "0090" and "089", with values 90 and 89. Return true if such a split exists and false otherwise.
Examples
Input: s = "4321" Output: true
Splitting into 4, 3, 2 and 1 gives consecutive descending values.
Input: s = "532" Output: false
The splits 5|32, 53|2 and 5|3|2 all have a neighboring pair that does not differ by exactly 1.
Input: s = "0090089" Output: true
"0090" and "089" have values 90 and 89.
Constraints
- 1 <= len(s) <= 20
- s consists of digits only
Approaches
- Baseline: try every set of cut points — time O(2^n · n), space O(n)
Follow-up
The search is almost linear because every value after the first is forced. If the gap between pieces could be any positive number, the second piece would also be a free choice, and the search would branch twice before becoming forced.
Related problems
Start free on Cariara · Coding problems · System design studio
