Part 1: Notations
$$$s$$$: The original string that might contain '?'.
$$$s[i,j] (i \leq j)$$$: The substring including $$$s[i]$$$ and $$$s[j]$$$: $$$(s[i], s[i+1],..., s[j])$$$.
$$$t$$$: The query string.
We also define some notations that will be clarified in the Part 2:
$$$ok[i,j]$$$: A $$$2D$$$ bool array indicating whether $$$s[i,j]$$$ is valid or not. We will define the word "valid" in Part 2. If $$$s[i,j]$$$ is valid, then $$$ok[i,j]$$$ is true, if $$$s[i,j]$$$ is invalid, then $$$ok[i,j]$$$ is false.
$$$set[i, j]$$$: The required character set to make $$$s[i,j]$$$ a palindrome.
$$$free[i, j]$$$: The number of free places. We will define the terminology "free places" in part 2.
Part 2: ok, set and free
We call a substring $$$s[i,j]$$$ valid if and only if:
For every $$$x$$$ such that
Unable to parse markup [type=CF_MATHJAX]
, ifUnable to parse markup [type=CF_MATHJAX]
, thenUnable to parse markup [type=CF_MATHJAX]
.
