PalindromfulString

SRM 496 · 2010-11-01 · by gojira_tc

SRM 496 · 2010-11-01 · by gojira_tc · Brute Force, Recursion, Simple Math

Show categories

Class Name: PalindromfulString

Return Type: long

Method Name: count

Arg Types: (int, int, int)

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.

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

Submissions are judged against all 131 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PalindromfulString with a public method long long count(int N, int M, int K) · 131 test cases · 2 s / 256 MB per case