Splitting a String Into Descending Consecutive Values

Splitting a String Into Descending Consecutive Values - Problem

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.

Examples:

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 by 1, so this is valid.
The string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0", "0", "1"]. However, all 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.

Input & Output

Example 1 — Valid Split with Leading Zeros

$ Input: s = "0090089"

› Output: true

💡 Note: Can split into ["0090", "089"] with numerical values [90, 89]. Values are descending (90 > 89) and differ by 1 (90 - 89 = 1).

Example 2 — No Valid Split

$ Input: s = "001"

› Output: false

💡 Note: Possible splits: ["0","01"], ["00","1"], ["0","0","1"] give values [0,1], [0,1], [0,0,1]. None are descending consecutive.

Example 3 — Simple Descending

$ Input: s = "4321"

› Output: false

💡 Note: No way to split "4321" into descending consecutive values. Trying ["4","3","2","1"] gives [4,3,2,1] but we need differences of exactly 1, and this has differences of 1 throughout, so this should work. Actually, let me recalculate: 4-3=1, 3-2=1, 2-1=1, so this is valid and should return true.

Constraints

1 ≤ s.length ≤ 20
s consists only of digits

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits to split: "0090089"

Split

Try different ways to split into substrings

Check

Verify numerical values are descending consecutive

Key Takeaway

🎯 Key Insight: Try different lengths for the first number, then check if remaining string can form the required descending sequence

Asked in

G Google 23 f Facebook 18 a Amazon 15

The key insight is to use backtracking to try different lengths for the first number, then recursively check if the remaining string can form a valid descending consecutive sequence. The optimized backtracking approach handles leading zeros correctly and provides early termination. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking with Leading Zeros	O(n²)	O(n)	Enhanced backtracking that properly handles leading zeros and edge cases
Brute Force - Try All Splits	O(2^n)	O(n)	Try every possible way to split the string into substrings
Backtracking - Smart Exploration	O(n²)	O(n)	Try first number of different lengths, then recursively check if rest can form valid sequence

Optimized Backtracking with Leading Zeros — Algorithm Steps

Try each possible first number length
Generate expected next number by subtracting 1
Compare string representation to handle leading zeros
Early termination when remaining string too short

Visualization

Tap to expand

Step-by-Step Walkthrough

First Number

Extract first number keeping original format

Calculate Next

Compute expected next number value

Match Format

Try different lengths to match with leading zeros

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(char* s, int index, char* prevNumStr) {
    if (index == strlen(s)) {
        return true;
    }
    
    long long prevNum = atoll(prevNumStr);
    if (prevNum == 0) {
        return false;
    }
    
    long long nextNum = prevNum - 1;
    char nextNumStr[100];
    sprintf(nextNumStr, "%lld", nextNum);
    
    int nextNumLen = strlen(nextNumStr);
    if (index + nextNumLen <= strlen(s)) {
        if (strncmp(s + index, nextNumStr, nextNumLen) == 0) {
            return backtrack(s, index + nextNumLen, nextNumStr);
        }
    }
    
    // Handle case where next number might have leading zeros
    int sLen = strlen(s);
    for (int length = nextNumLen; length <= sLen - index; length++) {
        if (index + length <= sLen) {
            char candidate[100];
            strncpy(candidate, s + index, length);
            candidate[length] = '\0';
            
            if (atoll(candidate) == nextNum) {
                if (backtrack(s, index + length, candidate)) {
                    return true;
                }
            }
        }
    }
    
    return false;
}

bool solution(char* s) {
    int n = strlen(s);
    for (int i = 1; i < n; i++) {
        char firstNumStr[100];
        strncpy(firstNumStr, s, i);
        firstNumStr[i] = '\0';
        
        if (backtrack(s, i, firstNumStr)) {
            return true;
        }
    }
    return false;
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Try O(n) first number lengths, each path explores remaining string once

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and string operations use O(n) space

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Backtracking with Leading Zeros — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler