Countdown Digit String

MediumBacktracking

Problem

A digit string s is a countdown if it can be cut into two or more consecutive pieces whose numeric values (leading zeros allowed, so "007" is 7) form a sequence where each value is exactly 1 less than the previous one.

Return true if s is a countdown, otherwise false.

Example 1

Input:
s = "050043"
Output:
true

"05" | "004" | "3" has values 5, 4, 3.

Example 2

Input:
s = "1234"
Output:
false

The values must decrease, not increase.

Constraints

  • 1 ≤ s.length ≤ 20
  • s contains only digits.

Hint

Show the first hint

Once the first piece is chosen, is there any freedom left for the rest?

Walkthrough

How to approach it

01Clarify before coding

  • Do leading zeros matter? No, "004" is 4.
  • Is a single piece enough? No, at least two pieces.
  • How big can a piece be? Up to 19 digits, beyond 2^53, so JavaScript numbers are not exact.

02Brute force

Try all 2^(n-1) ways to cut the string and check each sequence of values.

Cost: O(n · 2^n): about 10 million cut patterns for n = 20.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.