BadSubstring | Topcoder Archive

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
```
```
Returns: 1
```
The only string of length 0 is the empty string, and it doesn't have "ab" as a substring.
```
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.
```
29
```
```
Returns: 1548008755920
```

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.