TopCoder Statistics - Problem Statement

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
"ABCDEFGHABC"

Returns: 35
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 5322941
"ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXY"

Returns: 456975
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Returns: 26
"ABCDEFGHIJKLMNABCDEFGHIJKLMNABCDEFGHIJKLMNOPQRSTUVWXYOPQRSTUVWXYOPQRSTUVWXY"

Returns: 5101
"ABCABCDEFGHIJKLMNOPQRSTUVWDEFGHIJKLMNOPABCDEFGHIJKLMNOPQRSTUVWQRSTUVW"

Returns: 15289
"ABCDEFAAAAAAGHIJBBBBBCCCCCBBLMNOPQRSTUVW"

Returns: 3405
"BDCACBCACDBADBADCABDCBDDBABBABCBDBDBBABBDDBAADDBABADCDCD"

Returns: 1943036
"AAABBBBBAABABBAAAABBAAAABAABBAABBAB"

Returns: 9081146
"WNUXUNXWUNUNUUWXNUXNWUNUXWNUXUNXWUNUNUUWXNUXNWUNUXWNUXUNXWUNUNUUWXNUXNWUNUXWNUXUNXWUNUNUUWXNUXNWUNUX"

Returns: 931383

Statistics

Problem Statement for "PalindromicSubsequences"

Problem Statement

Definition

Constraints

Examples