TopCoder problem "BadSubstrings" used in TCCC05 Finals (Division I Level One)



Problem Statement

    

Consider strings constructed from the letters 'A', 'B', and 'C'. You will be given an integer N and two forbidden substrings, bad1 and bad2. You are to calculate the number of strings of length N that do not contain either substring. Note that a substring need not be shorter than the string in which it is contained (e.g., "AB" is a substring of "AB").

 

Definition

    
Class:BadSubstrings
Method:howMany
Parameters:int, String, String
Returns:long
Method signature:long howMany(int N, String bad1, String bad2)
(be sure your method is public)
    
 

Constraints

-N is between 1 and 39, inclusive.
-bad1 contains between 1 and 39 characters, inclusive.
-bad2 contains between 1 and 39 characters, inclusive.
-Each character in bad1 is 'A', 'B', or 'C'.
-Each character in bad2 is 'A', 'B', or 'C'.
 

Examples

0)
    
3
"AB"
"BA"
Returns: 17
There are 17 three-letter strings that do not contain "AB" or "BA", shown below: 
   AAA AAC ACA ACB ACC
   BBB BBC BCA BCB BCC
   CAA CAC CBB CBC CCA CCB CCC
1)
    
2
"A"
"BB"
Returns: 3
2)
    
5
"ABC"
"ABB"
Returns: 189
3)
    
39
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"ABCABCABCABCABCABCABCABCABCABCABCABCABC"
Returns: 4052555153018976265

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6554&pm=4018

Writer:

vorthys

Testers:

PabloGilberto , lbackstrom , Yarin

Problem categories:

Dynamic Programming