Problem Statement
Consider a string of length N which contains only uppercase letters. Write down all of its contiguous substrings of length M (a separate substring must be written down for each starting position, even if some of these substrings are the same strings). If at least K of the substrings you have written down are palindromes, we call the string palindromful.
Return the number of different palindromful strings of length N.
Definition
- Class:
- PalindromfulString
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long count(int N, int M, int K)
- (be sure your method is public)
Constraints
- N will be between 2 and 11, inclusive.
- M will be between 2 and N, inclusive.
- K will be between 0 and 11, inclusive.
Examples
2
2
1
Returns: 26
For a string of length 2, the only substring of length 2 is the string itself. Therefore, in this case we need to count palindromes of length 2, which are "AA", "BB", ..., "ZZ".
2
2
0
Returns: 676
This time there can be no palindrome among the substrings, so any string of length 2 will do.
3
2
1
Returns: 1326
Either the first two or the last two characters of the string should be equal, with no restrictions on the remaining one. This gives us 2*26*26=1352 variants, of which 26 are strings consisting entirely of the same character and therefore duplicated.
4
4
1
Returns: 676
We're looking for palindromes of length 4.
7
3
3
Returns: 4310176
11
2
0
Returns: 3670344486987776
11
2
1
Returns: 1190791264331526
11
2
3
Returns: 20442143237776
11
2
4
Returns: 1399174487776
11
2
5
Returns: 66166675276
11
2
6
Returns: 2182300276
11
2
8
Returns: 737776
11
2
10
Returns: 26
11
2
11
Returns: 0
11
3
1
Returns: 1091609135425276
11
3
2
Returns: 163264408862776
11
3
4
Returns: 865971362776
11
3
8
Returns: 152776
11
4
1
Returns: 43213517317776
11
4
2
Returns: 220200491576
11
4
4
Returns: 63029226
11
5
0
Returns: 3670344486987776
11
5
1
Returns: 37839705612176
11
5
2
Returns: 165023937676
11
5
6
Returns: 34476
11
6
0
Returns: 3670344486987776
11
6
1
Returns: 1252786085226
11
6
2
Returns: 174437926
11
6
3
Returns: 1811576
11
6
5
Returns: 1326
11
6
6
Returns: 26
11
6
7
Returns: 0
11
7
1
Returns: 1044017932776
11
7
3
Returns: 1352676
11
8
0
Returns: 3670344486987776
11
8
9
Returns: 0
11
9
4
Returns: 0
11
9
2
Returns: 51376
11
9
1
Returns: 24095378476
11
10
0
Returns: 3670344486987776
11
10
1
Returns: 617831526
11
10
2
Returns: 26
11
11
0
Returns: 3670344486987776
11
11
1
Returns: 308915776
11
11
11
Returns: 0
10
2
1
Returns: 41984966747126
10
2
2
Returns: 6279400340876
10
2
3
Returns: 566509715876
10
2
6
Returns: 34715876
10
2
9
Returns: 26
10
3
0
Returns: 141167095653376
10
3
1
Returns: 38017681590876
10
3
4
Returns: 19087840876
10
3
6
Returns: 11965876
10
3
7
Returns: 135876
10
4
0
Returns: 141167095653376
10
4
1
Returns: 1455373292776
10
4
2
Returns: 6347074526
10
4
5
Returns: 52676
10
4
10
Returns: 0
10
5
1
Returns: 1248382010876
10
5
2
Returns: 4528457076
10
5
3
Returns: 50514776
10
6
0
Returns: 141167095653376
10
6
1
Returns: 40154535876
10
6
2
Returns: 4461626
10
6
3
Returns: 52026
10
7
3
Returns: 34476
10
8
1
Returns: 926745326
10
8
2
Returns: 1976
10
9
1
Returns: 617830876
10
10
0
Returns: 141167095653376
10
10
1
Returns: 11881376
9
2
4
Returns: 734147726
9
2
5
Returns: 23210226
9
2
7
Returns: 5226
9
3
6
Returns: 118976
9
4
1
Returns: 48014692726
9
5
2
Returns: 115934676
9
6
1
Returns: 1235559026
9
6
3
Returns: 1326
9
9
1
Returns: 11881376
9
9
2
Returns: 0
8
2
0
Returns: 208827064576
8
2
3
Returns: 370033326
8
2
4
Returns: 14564576
8
2
7
Returns: 26
8
3
1
Returns: 43788002076
8
3
3
Returns: 217689576
8
5
2
Returns: 2670876
8
7
2
Returns: 676
8
8
1
Returns: 456976
6
2
1
Returns: 55009526
6
2
4
Returns: 3276
6
2
5
Returns: 26
6
3
4
Returns: 676
6
4
2
Returns: 1976
6
4
3
Returns: 26
6
6
1
Returns: 17576
7
2
0
Returns: 8031810176
7
2
1
Returns: 1684153926
7
2
4
Returns: 247676
7
3
1
Returns: 1430247676
7
4
1
Returns: 47421426
7
5
3
Returns: 676
7
7
1
Returns: 456976
7
7
7
Returns: 0
5
2
0
Returns: 11881376
5
2
1
Returns: 1725126
5
2
4
Returns: 26
5
3
1
Returns: 1318876
5
3
2
Returns: 51376
5
3
3
Returns: 676
5
4
1
Returns: 35126
5
4
2
Returns: 26
5
5
1
Returns: 17576
4
2
0
Returns: 456976
4
2
1
Returns: 50726
4
2
2
Returns: 1976
4
2
3
Returns: 26
4
3
0
Returns: 456976
4
3
1
Returns: 34476
4
3
2
Returns: 676
4
3
11
Returns: 0
3
2
0
Returns: 17576
3
2
2
Returns: 26
2
2
11
Returns: 0
2
2
10
Returns: 0
11
5
5
Returns: 1369576
11
4
7
Returns: 1326
11
8
5
Returns: 0