ConsecutivePalindromes | Topcoder Archive

Problem Statement

A palindrome is a word that reads the same forwards and backwards. For example, "Z", "ABBA", "RACECAR", and "XXXXXX" are all palindromes.

You are given a String S. A sequence of integers L is called a consecutive palindromic sequence for S if it has the following properties:

L is a strictly increasing sequence.
All elements of L lie between 0 and length(S)-1, inclusive.
L contains a subsequence of two or more consecutive integers (a, a+1, ..., b) such that the string S[a]S[a+1]...S[b] is a palindrome.

For example, for S = "TOPPAPPOT" the following sequences are some of the consecutive palindromic sequences: (2, 3), (0, 5, 6), (3, 4, 5), and (0, 1, 2, 3, 4, 5, 6, 7, 8). The sequences (0, 8) and (0, 1) are not consecutive palindromic sequences: they do not have the third property.

Let C be the number of consecutive palindromic sequences for the given string S. Compute and return the value (C modulo 10^9+7).

Definition

Class:: ConsecutivePalindromes
Method:: countStrings
Parameters:: String
Returns:: int
Method signature:: int countStrings(String S)
(be sure your method is public)

Constraints

S will contain between 1 and 2,000 characters, inclusive.
S will contain only uppercase English letters ('A' - 'Z').

Examples

```
"AAA"
```
```
Returns: 3
```
The three consecutive palindromic sequences are the sequences (0, 1), (1, 2), and (0, 1, 2). For example, the entire sequence (0, 1) corresponds to the palindrome S[0]S[1] = "AA". Note that the sequence (0, 2) is not a consecutive palindromic sequence: it does not contain any subsequence of two or more consecutive integers at all.
```
"ABCDEF"
```
```
Returns: 0
```
```
"BBAA"
```
```
Returns: 7
```
The seven consecutive palindromic sequences: (0, 1), (0, 1, 2), (0, 1, 3), (0, 1, 2, 3), (0, 2, 3), (1, 2, 3), and (2, 3). For example, (0, 2, 3) is a consecutive palindromic sequence because it contains the subsequence (2, 3): two consecutive integers with the property that S[2]S[3] = "AA" is a palindrome.
```
"ABCBA"
```
```
Returns: 4
```
```
"TOPPAPPOT"
```
```
Returns: 240
```

"AYUEOPPOLAKIKIKIUYOPZOOLPPPPKMOPOLIURKMQOAPLFKTURIWOOWWWPLOLWWWOPSLAA"

Returns: 216072426

```
"Z"
```
```
Returns: 0
```

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.