call(back)
Algorithms & Data StructureshardSign in to star problems

Reverse Count-and-Say I

The count-and-say step reads a digit string run by run and writes count then digit for each run: "23" -> "1213" (one 2, one 3); "3" repeated 121 times -> "1213" as well; "11" -> "21"; "0" -> "10".

You are given a string s that is the output of exactly one such step. Return all original strings that produce s.

A valid parse of s

  • s splits left to right into pairs (count, digit): count is a positive integer with no leading zero (multi-digit counts like "121" are legal), digit is exactly one character 0-9.
  • Consecutive pairs must have different digits — equal digits would have been one longer run.
  • If s cannot be parsed, return []. s = "" returns [""], keeping the round trip consistent.
"1213"  => ["23", "3" x 121]     (12,1)(3…) leaves a lone digit — invalid
"11"    => ["1"]
"21"    => ["11"]
"10"    => ["0"]
"11112" => ["1" x 11 + "2", "1" + "2" x 11, "2" x 1111]
          (1,1)(1,1)(1,2) is rejected: two consecutive runs of "1"
"0", "01", "1", "a1"  =>  []

Return the originals sorted ascending. Originals can be exponentially long, so build them as (count, digit) runs and expand at the end — s stays short (<= 20) when materializing.

Hints

Hint 1

Scan positions: at index i, the count is s[i..j) and the digit is s[j], for every j > i — then recurse from j + 1. A count may not start with "0".

Hint 2

Carry the previous digit through the recursion and reject a pair whose digit equals it — that is the forward step's maximal-run rule reflected backward.

Asked at