コンテンツにスキップ

回文

タグ「回文」の記事 1 件

牛客小白月赛138 B - Is it Palidrome?

英小文字と ? からなる長さ nn の文字列 ss があります。それぞれの ? を好きな英小文字に置き換えます。

  • どう置き換えても回文になるなら certainly
  • どう置き換えても回文にならないなら impossible
  • 回文になる置き換え方とならない置き換え方の両方があるなら possible

を出力してください(nn の総和 ≤5×105\le 5 \times 10^5)。

回文かどうかは、左右対称な位置にある文字のペア (si,sn−1−i)(s_i, s_{n-1-i})(0≤i<⌊n/2⌋0 \le i < \lfloor n/2 \rfloor)がすべて等しいかどうかで決まります。そこで、ペアを次の 3 種類に分けます。

  • どちらも英小文字で、異なる:どう置き換えてもこのペアは等しくならないので、回文にはなりません。
  • 少なくとも一方が ?:? の置き換え方しだいで、等しくすることも異なるものにすることもできます。
  • どちらも英小文字で、等しい:どう置き換えてもこのペアは等しいままです。

ペアごとの ? の置き換えは互いに独立に選べるので、答えは次のようになります。

  1. 異なる英小文字のペアが 1 つでもあれば impossible
  2. そうでなく、? を含むペアが 1 つでもあれば possible(すべてのペアを等しくすることも、そのペアだけを異なるものにすることもできる)
  3. どちらでもなければ certainly

nn が奇数のときの真ん中の文字はどのペアにも入らないので、? であっても回文かどうかに影響しません。3 つ目のサンプル xy?yx が certainly になるのはこのためです。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
p = False
ng = False
for i in range(N//2):
if S[i] == "?":
p = True
continue
if S[N-i-1] == "?":
p = True
continue
if S[i] != S[N-i-1]:
ng = True
continue
if ng:
print("impossible")
elif p:
print("possible")
else:
print("certainly")

p は ? を含むペアがあるか、ng は異なる英小文字のペアがあるかを表します。ループを N//2 までにしているので、真ん中の文字は自然に見ないことになります。