Problem link, link: https://codeforces.net/contest/1679/problem/E
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
(1)We call a substring $$$s[i,j]$$$ invalid if and only if:
there exists an index $$$x (i \leq x \leq j)$$$ such that s[x] != '?' && s[i+j-x] != '?' && s[x] != s[i+j-x]
.
For example,
"ab?a" is valid.
"ax?xc" is invalid because the first character 'a' mismatches with the last character 'c'.
"tbct" is invalid because 'b' != 'c'
The validity of a substring is irrelevant to the query subset. For example, if the query set $$$t$$$ does not contain the character 'b', we still call the string "ab?a" valid, although it certainly cannot form a palindrome. We will deal this case using the $$$set$$$ array.
(2) $$$set[i, j]$$$ denotes all the characters needed to make $$$s[i, j]$$$ a palindrome. For example, if s[i, j] == "ab?a"
, then set[i, j] == {b}
, as we need a character 'b' to fill in the '?'. Note that there are at most $$$17$$$ query characters in this problem, i.e., $$$|t| \leq 17$$$, so we can compress $$$set[i, j]$$$ to a $$$32$$$-bit integer to accelerate computation. Don't use std::set
!