Reverse Count-and-Say II
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 how many original strings 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, the answer is 0. s = "" has exactly one original, "".
"1213" => 2 ("23" and "3" x 121)
"11112" => 3 ((1,1)(1,1)(1,2) is rejected: two consecutive runs of "1")
"0" => 0s can be up to 2000 characters long, so the originals can't be listed — count them.
Hints
Hint 1
At index i, the count is s[i..j) and the digit is s[j], for every j > i. The number of parses from i onward depends only on i and the previous pair's digit.
Hint 2
Memoize ways(i, prevDigit): 1 at the end of the string, 0 when s[i] is not a digit or is "0", otherwise the sum over valid j of ways(j + 1, s[j]).
Hint 3
Up to 2000 characters means deep recursion — fill the table bottom-up from the end. A running total per digit turns the inner loop into a subtraction.