Problem Description

Given a string s consisting only of digits, your task is to determine if it is possible to split s into two or more non-empty substrings such that:

• Each substring represents a positive integer with no leading zeros.
• The integers form a strictly descending sequence, where each number is exactly one less than the previous one.
• All digits in s must be used, and substrings must not overlap or be reused.

Return true if such a split is possible, and false otherwise.

Example:
Input: s = "54321"
Output: true
Explanation: One possible split is ["5", "4", "3", "2", "1"].

Constraints:

• 1 <= s.length <= 20
• s consists only of digits ('0'-'9')

Thought Process

When approaching this problem, the first idea is to try every possible way to split the string into numbers and check if they form a descending consecutive sequence. Since the split points are not fixed and the numbers can have varying lengths, brute-forcing all possible splits seems feasible for small input sizes.

However, we want to avoid unnecessary work and make the process efficient. We can use recursion (backtracking) to systematically try all possible first numbers, then recursively check if the rest of the string can be split into the next descending value, and so on. If at any point we can't split further or the constraints are violated (e.g., leading zeros, non-consecutive numbers), we backtrack and try another split.

The main challenge is to efficiently try all valid splits, avoid invalid ones early, and return as soon as a valid sequence is found.

Solution Approach

We use a recursive backtracking algorithm to explore all possible splits of the input string s:

1. Pick the first number: Try all possible prefixes of s (from length 1 up to len(s) - 1) as the starting number. We stop at len(s) - 1 to ensure at least two substrings.
2. Recursive check: For each choice of the first number, recursively try to split the remaining string, always looking for the next number to be exactly one less than the previous.
3. Base case: If we've reached the end of the string and made at least two splits, return true.
4. Pruning: If a substring starts with '0' (and is longer than 1 digit), skip it (no leading zeros allowed). If the next number is not exactly one less, skip that split.
5. Backtracking: If a split fails, backtrack and try a different split.

This approach is efficient for the given constraints because the maximum string length is 20, making the recursion tree manageable.

Example Walkthrough

Let's walk through the input s = "05040302":

• Try first number: "0" (invalid, leading zero, skip)
• Try first number: "05" (invalid, leading zero, skip)
• Try first number: "050" (invalid, leading zero, skip)
• Try first number: "5"
• Next, look for "4" at the start of the remaining string "040302"
• Try "0" (invalid, leading zero, skip)
• Try "04" (invalid, leading zero, skip)
• Try "040" (invalid, leading zero, skip)
• Try "4"
• Next, look for "3" in "0302"
• Try "0" (invalid, leading zero, skip)
• Try "03" (invalid, leading zero, skip)
• Try "030" (invalid, leading zero, skip)
• Try "3"
• Next, look for "2" in "02"
• Try "0" (invalid, leading zero, skip)
• Try "02" (invalid, leading zero, skip)
• Try "2"
• End of string reached, splits are ["5", "4", "3", "2"]
• All are consecutive descending by 1. Return true.

This example shows how the recursive process finds a valid split by trying all possibilities and backtracking on invalid ones.

Time and Space Complexity

Brute-force approach: The number of ways to split a string of length n is exponential, as at each position we can choose to split or not. In the worst case, there are up to 2^{n-1} ways to split.

Optimized backtracking approach:
For each split, we only proceed if the next number is exactly one less and has no leading zeros, which prunes many branches. The number of recursive calls is still exponential in the worst case, but with n ≤ 20, this is acceptable.

• Time Complexity: O(2ⁿ), but pruned by constraints.
• Space Complexity: O(n) for the recursion stack.

Summary

To solve the problem of splitting a string into descending consecutive values, we use recursive backtracking to explore all possible splits, checking for valid descending sequences without leading zeros. The manageable input size allows this approach to work efficiently. The key insight is to prune invalid paths early and backtrack as soon as constraints are violated, making the solution both effective and elegant.

Code Implementation

class Solution:
    def splitString(self, s: str) -> bool:
        def dfs(start, prev, count):
            if start == len(s):
                return count >= 2
            for end in range(start + 1, len(s) + 1):
                curr_str = s[start:end]
                if len(curr_str) > 1 and curr_str[0] == '0':
                    break
                curr = int(curr_str)
                if prev is None or curr == prev - 1:
                    if dfs(end, curr, count + 1):
                        return True
            return False
        return dfs(0, None, 0)
      

class Solution {
public:
    bool dfs(const string& s, int start, long long prev, int count) {
        if (start == s.size())
            return count >= 2;
        for (int end = start + 1; end <= s.size(); ++end) {
            string curr_str = s.substr(start, end - start);
            if (curr_str.size() > 1 && curr_str[0] == '0')
                break;
            long long curr = stoll(curr_str);
            if (prev == -1 || curr == prev - 1) {
                if (dfs(s, end, curr, count + 1))
                    return true;
            }
        }
        return false;
    }
    bool splitString(string s) {
        return dfs(s, 0, -1, 0);
    }
};
      

class Solution {
    public boolean splitString(String s) {
        return dfs(s, 0, -1, 0);
    }
    private boolean dfs(String s, int start, long prev, int count) {
        if (start == s.length())
            return count >= 2;
        for (int end = start + 1; end <= s.length(); end++) {
            String currStr = s.substring(start, end);
            if (currStr.length() > 1 && currStr.charAt(0) == '0')
                break;
            long curr = Long.parseLong(currStr);
            if (prev == -1 || curr == prev - 1) {
                if (dfs(s, end, curr, count + 1))
                    return true;
            }
        }
        return false;
    }
}
      

var splitString = function(s) {
    function dfs(start, prev, count) {
        if (start === s.length) return count >= 2;
        for (let end = start + 1; end <= s.length; ++end) {
            let currStr = s.substring(start, end);
            if (currStr.length > 1 && currStr[0] === '0') break;
            let curr = Number(currStr);
            if (prev === null || curr === prev - 1) {
                if (dfs(end, curr, count + 1)) return true;
            }
        }
        return false;
    }
    return dfs(0, null, 0);
};