ConsecutivePalindromes
TCC India Online · 2017-07-25 · by boba5551
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
- 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).
Constraints
- S will contain between 1 and 2,000 characters, inclusive.
- S will contain only uppercase English letters ('A' - 'Z').
"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
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConsecutivePalindromes with a public method int countStrings(string S) · 57 test cases · 2 s / 256 MB per case