PalindromicSubstringsDiv1 | Topcoder Archive

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 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.

Definition

Class:: PalindromicSubstringsDiv1
Method:: expectedPalindromes
Parameters:: String[], String[]
Returns:: double
Method signature:: double expectedPalindromes(String[] S1, String[] S2)
(be sure your method is public)

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 ('?').

Examples

```
{"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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.