BadSubstrings | Topcoder Archive

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

```
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
```
2
```
```
"A"
```
```
"BB"
```
```
Returns: 3
```
```
5
```
```
"ABC"
```
```
"ABB"
```
```
Returns: 189
```

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

"ABCABCABCABCABCABCABCABCABCABCABCABCABC"

Returns: 4052555153018976265

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.