P2235 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There was a palindrome P, but some of its characters were replaced by ? to obtain the string S instead.
Given S, did there exist a unique parent palindrome P that could have resulted in S?

EXPLANATION:

The string P is a palindrome if and only if its opposite pairs of characters are equal.
In terms of indexing, if we treat P as a 1-indexed string of length N, this condition tells us that we want

P_i = P_{N+1-i}

for every 1 \le i \le N.

Now, let’s look at some index i in the string S.

  • If S_i and S_{N+1-i} are both existing characters, there’s nothing to talk about: the original string must have had P_i = S_i and P_{N+1-i} = S_{N+1-i}.
    So, the indices i and N+1-i are fixed.
  • If S_i = \texttt{?} but S_{N+1-i} is an existing character, then both P_i and P_{N+1-i} must have been equal to S_{N+1-i} in the original string.
    Again, the indices i and N+1-i are fixed.
  • Similarly, if S_i is an existing character but S_{N+1-i} = \texttt{?} then P_i and P_{N+1-i} both must’ve equalled S_i.
    Again, the indices i and N+1-i are fixed.
  • Finally, there’s the case of S_i = \texttt{?} and S_{N+1-i} = \texttt{?}.
    In this case, there are in fact many possible options: for example we could have P_i = P_{N+1-i} = \texttt{'a'} or P_i = P_{N+1-i} = \texttt{'b'}, and either option could result in the given S after overwriting.

Note that only the last option here is ambiguous.

So, if there exists an index i such that S_i = S_{N+1-i} = \texttt{?} then there are multiple possible original palindromes (so the answer is No); otherwise the original palindrome is unique and the answer is Yes.

If you’re using 0-indexing, then the opposite index of i is (N-1-i) instead, so check for S_i = S_{N-1-i} = \texttt{?}.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 'Yes'
    for i in range(n):
        if s[i] == '?' and s[n-1-i] == '?':
            ans = 'No'
    print(ans)