TopCoder problem "DeserializeSequence" used in SRM 230 (Division II Level Three)



Problem Statement

    Given a sequence of positive integers in nondescending order you can make a string by concatenating the sequence elements together. For example, the sequence [1,1,13,934] could become the string "01113934". Given a String str containing digits return how many distinct nondescending sequences could have produced str. Two sequences are distinct if they differ in some position, or have different lengths. When put into str, the sequence element could have been padded with leading zeros. For example, [1,2] could become "12", "00010002", "010002" as well as numerous other possible strings. You should assume the integers in the original sequence were between 1 and 1000000 inclusive.
 

Definition

    
Class:DeserializeSequence
Method:howMany
Parameters:String
Returns:int
Method signature:int howMany(String str)
(be sure your method is public)
    
 

Constraints

-str must contain between 1 and 50 characters inclusive.
-Each character of str must be a digit ('0' - '9').
 

Examples

0)
    
"1234"
Returns: 5
The 5 possible sequences are:
  [1,2,3,4]
  [1,2,34]
  [1,234]
  [1234]
  [12,34]
1)
    
"000000000001"
Returns: 1
[1] is the only possible sequence here.
2)
    
"1000000000000"
Returns: 0
No possible sequences.
3)
    
"9876543210"
Returns: 5
4)
    
"11111111111111111111111111111111111111111111111111"
Returns: 9192
5)
    
"10010010010010010010010010010010010010010010010010"
Returns: 1217

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3448

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6519&pm=3448

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Dynamic Programming