TopCoder problem "BadSubstring" used in SRM 178 (Division II Level Three)



Problem Statement

    Return how many strings containing length characters do not have the substring (quotes for clarity) "ab". The only characters allowed in the strings are 'a', 'b', and 'c'. A substring is any contiguous portion of a string. A substring may be empty, or the entire string.
 

Definition

    
Class:BadSubstring
Method:howMany
Parameters:int
Returns:long
Method signature:long howMany(int length)
(be sure your method is public)
    
 

Constraints

-length will be between 0 and 44 inclusive.
 

Examples

0)
    
0
Returns: 1
The only string of length 0 is the empty string, and it doesn't have "ab" as a substring.
1)
    
3
Returns: 21
There are 3*3*3=27 possible strings of length 3. 3 begin with ab, and 3 end with ab. The remaining 21 are all good.
2)
    
29
Returns: 1548008755920

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4710&pm=1872

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Dynamic Programming