PalindromfulString | Topcoder Archive

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

```
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
```

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.