PalindromicSubstringsDiv1
SRM 607 · 2013-12-22 · by Wheeler
Problem Statement
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
- 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.
Notes
- For each question mark, the letter used to replace it is chosen uniformly at random. That is, the probability of choosing any particular letter is 1/26. All random choices are mutually independent.
- A palindromic string is a string that reads the same forwards and backwards.
- Your return value must have an absolute or a relative error of less than 1e-9.
Constraints
- S1 and S2 will 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') and question marks ('?').
{"a","a",""}
{"a"}
Returns: 6.0
This is the example given in the statement.
{"z??"}
{}
Returns: 3.115384615384615
There are 26^2 = 676 equally likely possibilities for the letters used to replace the question marks. Here are all possible outcomes: The string "zzz" has 6 palindromic substrings. Each of the 25 strings "zaz", "zbz", ..., "zyz" has 4 palindromic substrings. Each of the 25 strings "zza", "zzb", ..., "zzy" has 4 palindromic substrings. Each of the 25 strings "zaa", "zbb", ..., "zyy" has 4 palindromic substrings. Each of the remaining 600 possible strings only has the 3 single-letter palindromic substrings. The expected number of palindromic substrings can be computed simply as the average over all 676 possible cases. Hence, the correct return value is (6 + 75*4 + 600*3) / 676.
{"ab","c"}
{"??","a?"}
Returns: 7.315088757396449
{}
{"?"}
Returns: 1.0
{"ab?def","?"}
{"f??a"}
Returns: 12.545971779699588
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PalindromicSubstringsDiv1 with a public method double expectedPalindromes(vector<string> S1, vector<string> S2) · 94 test cases · 2 s / 256 MB per case