Splitting a String Into Descending Consecutive Values

How it works

Instead of using recursion with the call stack, we can simulate the same process with an explicit stack. This converts the recursive solution into an iterative one, which can be useful for avoiding stack overflow on very deep recursions and makes the state transitions more explicit.

Steps

1. For each possible first number, push the state (next index, first number value) onto the stack.
2. While the stack is not empty, pop a state containing the current index and previous value.
3. Build numbers starting from the current index. When a number equals prev - 1:
   • If this number uses all remaining characters, return true.
   • Otherwise, push the new state (next index, current number) onto the stack.
4. Apply the same pruning: if the number grows to be greater than or equal to prev, stop building.
5. If all possibilities are exhausted without finding a valid sequence, return false.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n)

Things to watch for

Integer Overflow with Large Numbers

The string can be up to 20 characters long, meaning numbers can exceed 64-bit integer limits. Using int or even standard long without considering overflow can produce incorrect comparisons. Use unsigned long long or language-specific big integer handling, and be cautious when building numbers digit by digit.

Not Requiring At Least Two Parts

The problem requires splitting into at least two parts. A common mistake is returning true when the entire string forms a single number. Always ensure the loop for the first number excludes the last character, forcing at least one more part to exist.

Missing the Pruning Optimization

Without early termination when the current number exceeds or equals the previous number, the solution explores many unnecessary branches. Since we need strictly descending consecutive values, once num >= prev, no valid sequence can be formed by adding more digits, so breaking out of the loop is essential for efficiency.

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)
        stack = []
        val = 0

        for i in range(n - 1):
            val = val * 10 + int(s[i])
            stack.append((i + 1, val))

            while stack:
                index, prev = stack.pop()
                num = 0
                for j in range(index, n):
                    num = num * 10 + int(s[j])
                    if num + 1 == prev:
                        if j + 1 == n:
                            return True
                        stack.append((j + 1, num))
                    elif num >= prev:
                        break

        return False

class Solution {
public:
    bool splitString(string s) {
        int n = s.size();
        stack<pair<int, long long>> stack;
        unsigned long long val = 0;

        for (int i = 0; i < n - 1; i++) {
            val = val * 10 + (s[i] - '0');
            stack.push({i + 1, val});

            while (!stack.empty()) {
                auto [index, prev] = stack.top();
                stack.pop();
                unsigned long long num = 0;

                for (int j = index; j < n; j++) {
                    num = num * 10 + (s[j] - '0');
                    if (num + 1 == prev) {
                        if (j + 1 == n) {
                            return true;
                        }
                        stack.push({j + 1, num});
                    } else if (num >= prev) {
                        break;
                    }
                }
            }
        }

        return false;
    }
};