文字列 \(S\) がa のみからなっているとき 、明らかに \(S\) は回文ですので、Yes を出力します。

以下、\(S\) に a 以外の文字が含まれる場合について考えます。 一番愚直な方針としては先頭に a を付け加えなかった時、\(1\) つ加えた時、\(\ldots\) と試す方法があります。ここで、 \(\lvert S\rvert\) 個以上 \(a\)を付け加えると a でない文字と対称な位置に a が来てしまう事から \(\lvert S \rvert-1\) 個以下の場合について調べればよいです(参考 : ABC198-B) 。しかし、回文の判定には基本的に \(O(\lvert S\rvert)\) だけ計算量がかかるため、全体で最悪 \(O(\lvert S\rvert^2)\) かかり、これでは時間制限にかかってしまいます。

そこで、a を付け加える個数としてあり得るものが絞れないか考えてみます。ここで、文字列\(X\) について、先頭から見て \(1\) 文字目から \(i\) 文字目までがすべて a であり、\(i+1\)文字目が a でないとき、\(i\) を「\(X\)において先頭から連続するa の個数」という事にします (ただし、\(1\) 文字目が a でないならば \(i=0\) ) 。「末尾から連続するa の個数」についても同様に定義します。このとき回文であるような文字列 \(T\) について、\(T\)において先頭から連続するa の個数と末尾から連続する a の個数は等しくなければなりません。

一方で、\(S\) において先頭から連続する a の個数を \(x\), 末尾から連続する a の個数を \(y\) とし、\(S\) に a を \(k\) 個 \((0\leq k)\) 付け加えた文字列を\(S_k\) とすると、\(S\) には a でない文字が含まれていることから、\(S_k\) において先頭から連続する a の個数は \(x+k\), 末尾から連続する a の個数は \(y\) となります。

よって、\(x>y\)ならば \(S\) の先頭にいくつ a を付け加えても回文となる事はなく、\(x\leq y\) のとき、\(S_k\)が回文となり得るのは\(k=y-x\) のときだけです。よって、この場合は \(S_{y-x}\) についてだけ回文かを判定すればよいです。

\(x\), \(y\) の値は \(O(\lvert S\rvert)\) で求めることができ、\(S\) にa を \((y-x)\) 個付け加えた時の回文判定も \(O(\lvert S\rvert)\) で行えるため、全体で時間計算量は \(O(\lvert S\rvert)\) であり、よってこの問題を解く事が出来ました。

c++による実装例:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, x, y;
	string a;

	cin >> a;
	n = a.size();

	x = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 'a')x++;
		else break;
	}
	y = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] == 'a')y++;
		else break;
	}

	if (x == n) {
		cout << "Yes" << endl;
		return 0;
	}
	if (x > y) {
		cout << "No" << endl;
		return 0;
	}
	for (int i = x; i < (n - y); i++) {
		if (a[i] != a[x + n - y - i - 1]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}