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 String[]s S1 and S2 as follows:
- 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. |