Problem statement

https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/

Solution

The idea is to use dp with states dp(i, num), where we try to split string s[i:] such that it starts with num.

Complexity

We have at most n values for i and upto n values for num. So, it total we have O(n^2) states, each of them have O(n) transitions, each of which needed O(n) time to process num, because numbers can have length upto n. So, total time complexity is O(n^4), space is O(n^3).

Code

class Solution:
    def splitString(self, s):
        n = len(s)
        
        @lru_cache(None)
        def dp(i, num):
            if i == n: return 0
            ans = -float("inf")
            for j in range(i + 1, n+1):
                if int(s[i:j]) == num - 1:
                    ans = max(ans, 1 + dp(j, num - 1))
            return ans
        
        for i in range(1, n):
            if dp(i, int(s[:i])) > 0: return True
            
        return False