Longest Palindromic Substring Replacement

You are given a string of length \(n\) consisting of lowercase letters and asterisks ('*'). You are also given a set of allowed characters of size \(m\). You can replace each asterisk in the string with any character from the allowed set. Your task is to determine the length of the longest substring which can be transformed into a palindrome by appropriately replacing the asterisks.

A substring is a contiguous sequence of characters from the string. A palindrome is a string that reads the same forwards and backwards. In order to replace an asterisk, if it is paired with a fixed character, the replacement must match that character (and that fixed character must be in the allowed set) otherwise if both are asterisks, they can be replaced by any same allowed character.

Note: It is guaranteed that the fixed characters in the input string are among the allowed characters.

The transformation is applied only on the selected substring. Your goal is to maximize the length of the palindromic substring that can be obtained by choosing an optimal substring and replacing the asterisks within it appropriately.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the length of the string and the number of allowed characters, respectively.

The second line contains the string \(s\) of length \(n\) consisting of lowercase letters and asterisks ('*').

The third line contains \(m\) allowed characters separated by spaces.

outputFormat

Output a single integer representing the length of the longest palindromic substring that can be formed by replacing the asterisks with the allowed characters.

10 3
a*c*cdc*c*
a b c

9