We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Splitting a String Into Descending Consecutive Values

Difficulty: Medium

Problem Description

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. Return true if it is possible to split s as described above, or false otherwise.

Key Insights

  • The string must be split into at least two non-empty substrings.
  • The numerical values of the substrings need to be in strictly descending order.
  • The difference between adjacent numerical values must be exactly 1.
  • Leading zeros in substrings may affect their numerical value (e.g., "001" is 1).
  • A backtracking approach can be used to explore all possible splits.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, we might check all possible splits in a string of length n. Space Complexity: O(n) - The recursion stack could take up to O(n) space in the worst case.

Solution

To solve this problem, we can use a backtracking approach. The algorithm works by iterating through possible split points in the string, creating substrings, and checking if the numerical values satisfy the descending order and difference conditions. We maintain a previous number to compare with the current substring's numerical value. If we can make valid splits until the end of the string, we return true; otherwise, we return false.

Code Solutions

def can_split(s: str) -> bool:
    def backtrack(start: int, prev_num: int) -> bool:
        if start == len(s):
            return True
        
        for end in range(start + 1, len(s) + 1):
            substr = s[start:end]
            num = int(substr)
            
            # Check for leading zeros (except for the number '0' itself)
            if substr[0] == '0' and len(substr) > 1:
                continue
            
            # Check if the current number is valid
            if prev_num != -1 and num != prev_num - 1:
                continue
            
            # Recurse with the new start position and current number
            if backtrack(end, num):
                return True
        
        return False
    
    # Start the backtracking with an invalid previous number
    for i in range(1, len(s)):
        substr = s[:i]
        num = int(substr)
        
        if substr[0] == '0' and len(substr) > 1:
            continue
        
        if backtrack(i, num):
            return True
            
    return False
← Back to All Questions