PalindromicSubstringsDiv2
SRM 607 · 2013-12-22 · by Wheeler
Problem Statement
Marco recently learned about palindromic strings. A palindromic string is a string that reads the same forwards and backwards. For example, "radar" and "racecar" are palindromic strings.
Now Marco is excited about palindromic strings. In particular, he likes strings that have a lot of palindromic substrings. For example, he really likes the string "aaa" because it has 6 palindromic substrings: "a" occurs three times, "aa" occurs twice, and "aaa" occurs once.
Right now, Marco has a string S composed of lowercase letters.
You are to reconstruct S from the given
- Concatenate in order all elements of S1 to make a string A.
- Concatenate in order all elements of S2 to make a string B.
- Finally, concatenate A and B to get S.
Return the number of palindromic substrings in S.
Constraints
- S1 and S2 will each contain no more than 50 elements.
- Each element of S1 and S2 will contain no more than 50 characters.
- S will contain at least 1 character.
- S will contain only lowercase letters ('a' - 'z').
{"a","a",""}
{"a"}
Returns: 6
This is the example given in the statement, "aaa".
{"zaz"}
{}
Returns: 4
{"top"}
{"coder"}
Returns: 8
{}
{"daata"}
Returns: 7
There are five palindromic substrings of length 1, one of length 2 ("aa" starting at index 1), and one of length 3 ("ata" starting at index 2).
{"abccba"}
{}
Returns: 9
Submissions are judged against all 130 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PalindromicSubstringsDiv2 with a public method int count(vector<string> S1, vector<string> S2) · 130 test cases · 2 s / 256 MB per case