One-dimensional Dynamic Programming
When the state is a position in a string
The answer at each position depends on how the piece ending there could have been formed.
Key idea
The state sentence
For problems that consume a string according to rules, the state is usually a position and the answer is how many ways there are to consume everything up to it.
So the answer at position i is the number of valid ways to interpret the first i characters. The final answer is at the end, and the base case is one way to interpret nothing, which is the empty interpretation.
That base case of one, rather than zero, is the part people get wrong. There is exactly one way to do nothing, and setting it to zero makes every count collapse.
Why it works
Each rule contributes one term
To reach position i, the last piece consumed must have been of some allowed length. Each allowed length contributes the count from wherever that piece started.
So write one term per rule, each guarded by whether that piece is actually valid here. The recurrence is a sum of the terms whose guards pass.
Tip
Read the first result
There are two ways to cut aab using the allowed pieces: a then a then b, or aa then b. Restricting the allowed set to single characters leaves only one.
The third case has no valid cut at all and correctly returns zero rather than raising, because no guard ever passes and the counts stay at their initial value.
Gotcha
The guard is not just a length check
start >= 0 keeps the index in range, and it is not sufficient on its own. The piece also has to actually match the text at that position, which is the second half of the condition.
For problems where the validity rule is a range rather than a literal, such as a two-character piece needing to fall between two values, the guard is that range check. Writing the length check and forgetting the validity check produces counts that are too high, which is harder to notice than a crash.
Edge cases
The cases that break this family
Problems in this family almost always have a character or value that is valid alone but not in combination, or valid in combination but not alone. A leading zero in a numeric encoding is the classic one.
That means the two guards are genuinely different conditions rather than one shared test, and the input designed to catch you will have that character at the start, in the middle, and at the end. Write those three cases out before submitting.
Cost
Cost
One pass over n positions, doing work proportional to the number of rules at each, so O(n times r) for r rules. When the rules are a fixed small set, that is linear.
Space is the counts array, O(n), and it drops to a fixed number of variables when the rules only reach back a fixed distance, which is the usual case in this family.
Predict the output: which pieces are legal at each position
A digit string is scanned, and at each position the one and two character pieces ending there are tested against a set of legal codes. Type the four lines it prints.
Decode Ways
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.