Marco likes 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 and question marks.
You are to reconstruct S from the given String[]s S1 and S2 as follows:
- Concatenate all elements of S1 to make a string A.
- Concatenate all elements of S2 to make a string B.
- Finally, concatenate A and B to get S.
Marco is going to replace every question mark in S with a random lowercase letter ('a' - 'z').
Return the expected number of palindromic substrings in the resulting string. |