Splitting a String Into Descending Consecutive Values
MedPrompt
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 by1, 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 <= 20sonly consists of digits.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a recursive function, say
backtrack(index, current_partition), that explores all possible ways to partition the string. - The
indexparameter tracks the current position in the strings. - The
current_partitionis a list that stores the numerical values of the substrings in the partition being built. - The base case for the recursion is when
indexreaches the end of the string. At this point, check if thecurrent_partitionis 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
indexto the end of the string, creating every possible next substring. For each substring, it's parsed into a number, added tocurrent_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
trueimmediately.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.