LongPalindromes | Topcoder Archive

Problem Statement

There is a string written on a sheet of paper. Katka has an eraser. She would like to erase some (possibly none or all) of the characters in such a way that the remaining letters will form a palindrome. Count the number of ways in which she can do it.

There is a catch: Katka's string is very long.

You are given the int repeats and the String pattern. Katka's string is obtained by concatenating repeats consecutive copies of the string pattern.

Compute and return the number of ways in which Katka can produce a palindrome, modulo 10^9 + 7.

Definition

Class:: LongPalindromes
Method:: count
Parameters:: int, String
Returns:: int
Method signature:: int count(int repeats, String pattern)
(be sure your method is public)

Notes

A palindrome is a string that reads the same forwards and backwards. In particular, the empty string is also a palindrome.

Constraints

pattern will have between 1 and 50 characters, inclusive.
Each character in pattern will be a lowercase English letter ('a'-'z').
repeats will be between 1 and 10^9, inclusive.

Examples

```
1
```
```
"blob"
```
```
Returns: 8
```
The eight valid ways of erasing are the following ones (with periods representing erased letters): .... b... .l.. ..o. ...b b..b bl.b b.ob
```
1
```
```
"various"
```
```
Returns: 8
```
All the letters are distinct, so Katka must erase all except for at most one.
```
30
```
```
"aa"
```
```
Returns: 536396504
```
Katka's string consists of 60 occurrences of the letter 'a'. Each of the 2^60 possible ways of erasing some of them produces a palindrome.
```
3
```
```
"abac"
```
```
Returns: 343
```

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.