Problem Statement |
| A palindrome is a string that is the same whether it is read from left to right or from right to left.
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 |
0) | |
| | 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". |
|
|
1) | |
| | Returns: 676 | This time there can be no palindrome among the substrings, so any string of length 2 will do. |
|
|
2) | |
| | 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. |
|
|
3) | |
| | Returns: 676 | We're looking for palindromes of length 4. |
|
|
4) | |
| |