Countdown Hidden in Digits

Medium

You are given a string digits made of digits. Can you cut it into **two or more** non-empty pieces so that the numbers written in the pieces (leading zeros allowed) form a countdown, each one exactly 1 less than the one before? For example, "0201" cuts into "02" and "01", which are 2 and 1, so it works. "012" cannot work at all, because the numbers have to go down. Return True if such a cut exists, and False otherwise.

Example 1

digits='1110009' → True

Split into 11, 10, 009: the values 11, 10, 9 each drop by exactly one.

Example 2

digits='4320' → False

No cut works: 4, 3, 2, 0 breaks at the last step, and 43, 20 or 432, 0 are not consecutive.

Example 3

digits='00100' → True

Constraints

1 ≤ len(digits) ≤ 20
The string consists of digits only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Backtracking

Similar problems

Keypad Words Medium All Balanced Bracket Strings Medium Word Traced on a Letter Grid Medium IP Addresses From a Digit String Medium Cutting a Word Into Palindromes Medium

Input

digits='1110009'

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.