Problem statement

https://binarysearch.com/problems/Consecutively-Descending-Integers/

Solution

Choose as starting number s[:1], s[:2], ... and so on.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        def helper(s, n):
            if not s: return True
            if n < 0: return False
            sn = str(n)
            if s[:len(sn)] == sn:
                return helper(s[len(sn):], n - 1)
            return False

        for l in range(1, len(s)):
            n = int(s[:l])
            if helper(s[l:], n - 1):
                return True
        return False