日刊競プロ ABC 237 - C - kasaka-

C - kasaka

問題文
英小文字からなる文字列 S が与えられます。 S の先頭に a をいくつか（ 0 個でも良い）つけ加えて回文にすることができるか判定してください。ただし、長さ N の文字列 A=A1A2​…AN​が回文であるとは、すべての 1≤i≤N について Ai​=AN+1−i​
が成り立っていることをいいます。

制約
1≤∣S∣≤10**6
S は英小文字のみからなる。

考えたこと

まずは素直にaを付け加えて試してみると,10**6で間に合わない。

S = list(input())
length = len(S)
i = 0
while True:
 if str("".join(S))==str("".join(S))[::-1]:
   print ("Yes")
   quit()
 S.insert(0,"a")
 if i>length:
   break
 i+=1
print ("No")

解説を見て考えたこと

以下の解説動画を見てもしっくりこなかったが、その中であったコメントを見て納得した。

https://www.youtube.com/watch?v=sntAcA4Jbwo&t=2855s

それは「前後のaを捨てて回文　かつ　捨てた個数は後ろのaの方が前のaより多い」ということ

前からaを足していくので、後ろに並んでいるaより多い時点で回文にならない。なので前後でaが連続している個数を調べて、その時点で後ろのaの個数が多くなる必要がある。そしてaを消した場合に、真ん中の文字列が回文になっていれば大丈夫。

S = list(input())
length = len(S)
i = 0
x = 0
for i in range(len(S)):
 if S[i]=="a":
   x+=1
 else:
   break
re_S = S[::-1]
y=0
for i in range(len(S)):
 if re_S[i]=="a":
   y+=1
 else:
   break
del S[0:x]
re_S = S[::-1]
del re_S[0:y]
if x<=y and re_S==re_S[::-1]:
 print ("Yes")
else:
 print ("No")