Connection Status:
Competition Arena > PalindromicSubsequences

PalindromicSubsequences

TCO20 North America Qualifier · 2020-09-19 · by erinn

TCO20 North America Qualifier · 2020-09-19 · by erinn · Dynamic Programming
Class Name: PalindromicSubsequences
Return Type: int
Method Name: count
Arg Types: (string)
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.

Constraints

  • s will contain between 1 and 100 upper-case ('A'-'Z') characters.
Examples
0)
"AB"
Returns: 2

The best we can do here is to take either single letter as a palindrome.

1)
"ABA"
Returns: 5

We can take any single letter, the pair AA, or the whole string ABA, a total of 5 possibilities.

2)
"AAA"
Returns: 7

Any non-empty subsequence is a palindrome.

3)
"ABCBA"
Returns: 13
4)
"ABCDEFGHABC"
Returns: 35

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

Coding Area

Language: C++17 · define a public class PalindromicSubsequences with a public method int count(string s) · 14 test cases · 2 s / 256 MB per case

Submitting as anonymous