⚡Flashcard Drill➔
NeetCode #503LC-1849MediumBacktracking
← Back to All Problems

#503 · #1849 · Splitting a String Into Descending Consecutive Values(将字符串拆分为递减的连续值)

📌 Problem Statement & Constraints

Given a string s of digits, return true if it can be split into two or more non-empty substrings whose integer values form a strictly decreasing sequence where each value is exactly 1 less than the previous. Constraints: 2 <= s.length <= 20.

💡 Core Algorithmic Approaches

  1. Try every possible first substring, then recursively require each following substring to equal prev - 1.
  2. Because the required value is fixed, there is no branching after the first choice -- only the split position varies.
  3. A pruning: as the substring grows, its integer value increases, so once it exceeds prev - 1, longer substrings cannot work either.
  4. The answer requires at least two substrings, which the outer loop guarantees.

💻 Benchmark Python3 Implementation

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)

        def dfs(start: int, prev: int) -> bool:
            if start == n:
                return True                # the whole string was consumed
            for end in range(start, n):
                cur = int(s[start:end + 1])
                if cur == prev - 1 and dfs(end + 1, cur):
                    return True
                if cur >= prev:
                    break                  # longer substrings are even larger
            return False

        for end in range(0, n - 1):        # leave room for at least one more part
            first = int(s[:end + 1])
            if dfs(end + 1, first):
                return True
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): the first split has O(n) choices and each verification is O(n) amortised.
💾 Space Complexity
O(n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Allowing the first substring to consume the whole string: at least two parts are required, hence range(0, n - 1).
  • Using continue instead of break for the cur >= prev pruning: break is valid because longer substrings are strictly larger.
  • Forgetting that leading zeros are allowed: "10" splits into "1" and "0", since 0 = 1 - 1 -- the values need not have no leading zeros, only the values must satisfy the decrement rule. (Leading zeros inside a part are fine here.)
  • Requiring the sequence to be consecutive but not strictly decreasing by exactly 1: the rule is exactly prev - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems