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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Splitting a String Into Descending Consecutive Values

Number: 1976

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string s that consists only of digits, determine if it is possible to split s into two or more non-empty substrings such that the numerical values of these substrings form a strictly descending sequence with every adjacent pair differing exactly by 1. For example, s = "050043" can be split into ["05", "004", "3"] corresponding to numerical values [5, 4, 3].

Key Insights

  • The string must be partitioned into at least two substrings.
  • Leading zeros are permitted, so converting substrings to integer values must handle these properly.
  • A recursive backtracking approach can try every possible partition of the string.
  • The first substring can be any valid prefix and subsequent substrings must exactly equal the previous number minus one.
  • Given the maximum length of s is 20, an exponential backtracking solution is sufficiently efficient.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case scenario due to exploring all possible partitions.
Space Complexity: O(n) for the recursion call stack and local variables during backtracking.

Solution

The algorithm begins by trying each possible prefix of the string as the starting number. Then, using recursion (backtracking), it attempts to partition the rest of the string such that each subsequent number is exactly one less than the previous number. If at any point the sequence condition is violated or a partition fails, backtracking is used to try alternative splits. If the end of the string is reached while satisfying the constraints and having made at least one split, the solution returns true.

Code Solutions

# Python solution using backtracking.
class Solution:
    def splitString(self, s: str) -> bool:
        # Helper function for recursion: index is current position, prev is previous number.
        def backtrack(index: int, prev: int) -> bool:
            # If we've processed the whole string, we've found a valid split (only valid if prev != -1, i.e. at least one split done).
            if index == len(s):
                return True
            curr = 0
            # Try every possible partition from index to end
            for i in range(index, len(s)):
                curr = curr * 10 + int(s[i])  # Build current number
                # If we are at the start, or the current number is exactly prev - 1.
                if prev == -1:
                    if backtrack(i + 1, curr):
                        return True
                elif curr == prev - 1:
                    if backtrack(i + 1, curr):
                        return True
            return False
        
        return backtrack(0, -1)

# Example usage:
# solution = Solution()
# print(solution.splitString("050043"))
← Back to All Questions