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
39
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"ABCABCABCABCABCABCABCABCABCABCABCABCABC"
Returns: 4052555153018976265
39
"ABCABCABCABCABCABCABC"
"ABCABCABCABCABCABCABB"
Returns: 4052555138756162709
39
"AB"
"AAA"
Returns: 8274985766717123
10
"AAAAAAAAAAA"
"AAAAAAAAAAB"
Returns: 59049
39
"B"
"C"
Returns: 1
20
"A"
"AAAA"
Returns: 1048576
25
"ABA"
"ABACABA"
Returns: 366774776373
5
"ABCCA"
"CCBCCB"
Returns: 242
39
"ABBA"
"ABBA"
Returns: 2590527498630102910
31
"AABB"
"AAAAABBBBB"
Returns: 430664584028319
33
"CABACBBABAAC"
"ABBCCAACCBBCABACBCBABACB"
Returns: 5558830440320331
17
"AAAABBBB"
"AAAACBBBB"
Returns: 128884295
3
"ABBA"
"CBBA"
Returns: 27
10
"BBBAACC"
"BBCB"
Returns: 54000
11
"AAACCBAAABB"
"CBACACCA"
Returns: 177038
12
"CBCBABACA"
"BCCBCA"
Returns: 526231
13
"AAABABBBBAACB"
"BBAACBABABCC"
Returns: 1594316
14
"BCCBBBBCBCA"
"BABAABCCBCBA"
Returns: 4782834
15
"AABABCBC"
"AABBABBCCCB"
Returns: 14331006
16
"BCBAC"
"CAB"
Returns: 23104477
17
"AABBCCABAABCBA"
"CBBCBBACCB"
Returns: 129122559
18
"BBCBCBACCABC"
"ABBBAAAA"
Returns: 386766009
19
"CABABAACBBAABACBC"
"BBCBAAACCBBABBB"
Returns: 1162261035
20
"BABCACCBCCB"
"CCCAACCBABACCCA"
Returns: 3486586113
21
"ACB"
"CAABAC"
Returns: 4725542579
22
"ABBBBB"
"ABCABBCAACBB"
Returns: 30652512642
23
"AABBCAABBCCABBBCCACC"
"BAB"
Returns: 43814289067
24
"BABAABBBCBBAAB"
"BCBBBCBBCAACCBCCBCBBC"
Returns: 282428886834
25
"BCCBB"
"BCBCCBBBBABACB"
Returns: 776698458438
26
"ACBACBCC"
"BACACBBCA"
Returns: 2532187322997
27
"BCBABBABCCAACBBABBA"
"CCBCBAAAACBBABCCABBACBCACC"
Returns: 7625597425932
28
"BBBBAA"
"CBACCBABBCACAAACCAABCBC"
Returns: 22161597348465
29
"BCAABCACCABACCB"
"CBBCAAB"
Returns: 67910498912283
30
"ABCABAACBCBACAABCCBCBCACC"
"BBAAC"
Returns: 184655425783008
31
"CCCCBACABBCACAAABBABBCCBB"
"BACBAACABAABBCAABCCCCAAAACCBCAB"
Returns: 617673396278843
32
"BCA"
"ABCBAAAABBB"
Returns: 543900847913133
33
"CBACAACABCCBBACCCABBCAABAABBBBA"
"ABCBACABBACCCBBB"
Returns: 5559058242032571
34
"BBCAAABBCACBABABABABAABABACBBBBCAB"
"AABBACAAAAACACCCBACBAABCCCACAC"
Returns: 16677181699666163
35
"CABCAABCBBCAACACCA"
"BBCAC"
Returns: 43940196443101766
36
"CCBABCCCBCCBCCCCBBAACCBBACCACACABA"
"BCACCCCABBABCABCAACCC"
Returns: 150094635067416582
37
"ACBCCBBACCBBCABBCBACA"
"BCBAC"
Returns: 392158825419761847
38
"BABACACBCCBACBCAAB"
"CAA"
Returns: 310020756163394364
39
"AAABBBACCCBBAABCCC"
"AAACAACBCBACBBAAACB"
Returns: 4052554849668733767
10
"BBCCBCCA"
"BBCABAABCB"
Returns: 59021
11
"CAAC"
"AACC"
Returns: 148629
12
"CCCBAAAABA"
"BABCA"
Returns: 513972
13
"AAA"
"ACCAAABABCA"
Returns: 1171920
14
"CBAACBACCAC"
"CACCA"
Returns: 4592230
15
"BCC"
"CBBBAB"
Returns: 8333885
16
"ABAC"
"CBAABCBA"
Returns: 36376737
17
"CCABAB"
"ABAACBBBACAABB"
Returns: 127019394
18
"ACCCBCCCBACBAA"
"BAAABBAAAAACAAC"
Returns: 387419976
19
"BCBCCACABAA"
"BABBCC"
Returns: 1139960724
20
"CACBBAACCCBAA"
"CACCCBABCBCAB"
Returns: 3486749409
21
"BAC"
"CABAACCBCACBCCBCCAC"
Returns: 4822748397
22
"CBAACCACAABBBCAB"
"BBACCBACBACCCCBC"
Returns: 31381049403
23
"CBCCBABBAB"
"AABABCACABCBCBBACBCB"
Returns: 94120858467
24
"BCCCCAAAACCCBB"
"BACBAAAAA"
Returns: 282199324887
25
"CBBABCC"
"BCCBACBC"
Returns: 837659131174
26
"ACCCBCCAAB"
"ABACCAB"
Returns: 2518012844127
27
"CCCBA"
"BBBBBBAABBAACAAACABC"
Returns: 6925674980439
28
"ACBBAAABBCCBA"
"BBB"
Returns: 11190001005568
29
"BCCACCCBCCAABC"
"BCACAABBCCACBBAACBBCBCCB"
Returns: 68630147781030
30
"ACAACBBCCCABACBBCCABCAA"
"BABCCACBAABCBCA"
Returns: 205890902494642
31
"AAA"
"CABCBCCCABCCBBCAAABAA"
Returns: 278499418452992
32
"CCBAB"
"CCCCBCCBCACCBBBCBACCAB"
Returns: 1648018376789901
33
"BAABCBACCCCCBBC"
"ABBCCBCCBCBBAACCAABCABBCBABACBBCB"
Returns: 5559053205566501
34
"CBACACCCCACABA"
"ACBAAB"
Returns: 16022302387382355
35
"AACCBACBB"
"AAACCBCABCCCCCCCBABBAACCB"
Returns: 49962936802875714
36
"BAAABACCCBABACC"
"CCCBBBCCABCABCAABCCCBBBACBBB"
Returns: 150094405169190018
37
"ACACAACACBABAACAABAABBABBBAB"
"CCBCABABAABBCCBCBBABBBBCBBBACACAA"
Returns: 450283905890800128
38
"ABCACBACACACCBBAAA"
"BCBCBAACCACCBCCAAAACBACCBBABAABCBA"
Returns: 1350851644450519425
39
"AACC"
"CACACBACCCBACCBBBCCCCABCCCBAAACBCCAABA"
Returns: 2548194741936514812