PalindromicSubsequences | Topcoder Archive

Problem Statement

A palindrome is a sequence that can be read the same forwards and backwards. For example, ABBA and ABCBA are palindromes, while ABCAB and ACAB are not.

Given a String s, how many ways can a subsequence of letters be taken such that it forms a palindrome? Since this number may be large, return the value MOD 10000019.

Definition

Class:: PalindromicSubsequences
Method:: count
Parameters:: String
Returns:: int
Method signature:: int count(String s)
(be sure your method is public)

Constraints

s will contain between 1 and 100 upper-case ('A'-'Z') characters.

Examples

```
"AB"
```
```
Returns: 2
```
The best we can do here is to take either single letter as a palindrome.
```
"ABA"
```
```
Returns: 5
```
We can take any single letter, the pair AA, or the whole string ABA, a total of 5 possibilities.
```
"AAA"
```
```
Returns: 7
```
Any non-empty subsequence is a palindrome.
```
"ABCBA"
```
```
Returns: 13
```

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.