Problem Statement
A string of letters A, B, C is forbidden if there are three consecutive letters from which one is A, one is B, and one is C. For example, BAACAACCBAAA is forbidden, while AABBCCAABB is not.
Your task is to calculate how many such strings of length n are not forbidden.
Your task is to calculate how many such strings of length n are not forbidden.
Definition
- Class:
- ForbiddenStrings
- Method:
- countNotForbidden
- Parameters:
- int
- Returns:
- long
- Method signature:
- long countNotForbidden(int n)
- (be sure your method is public)
Constraints
- n will be between 1 and 30, inclusive.
Examples
2
Returns: 9
All 9 strings of length 2 are not forbidden.
3
Returns: 21
There are 27 strings of length 3. Of these, 6 contain one occurrence of each letter. Those 6 strings are forbidden, so you should return 21.
4
Returns: 51
1
Returns: 3
5
Returns: 123
10
Returns: 10089
20
Returns: 67858611
30
Returns: 456417007497
6
Returns: 297
7
Returns: 717
8
Returns: 1731
9
Returns: 4179
11
Returns: 24357
12
Returns: 58803
13
Returns: 141963
14
Returns: 342729
15
Returns: 827421
16
Returns: 1997571
17
Returns: 4822563
18
Returns: 11642697
19
Returns: 28107957
21
Returns: 163825179
22
Returns: 395508969
23
Returns: 954843117
24
Returns: 2305195203
25
Returns: 5565233523
26
Returns: 13435662249
27
Returns: 32436558021
28
Returns: 78308778291
29
Returns: 189054114603