If the string \(S\) consist of a only, then \(S\) is obviously a palindrome, so Yes should be printed.

On the other hand, consider the cases where \(S\) contains a character other than a. The naivest way is to try prepending no a’s, one a, \(\ldots\) and so on. If we prepend \(\lvert S\rvert\) or more \(a\)’s, we will have an a at the position symmetric to a non-a character, so it is sufficient to check all cases up to \(\lvert S \rvert-1\) a’s (see also: ABC198-B). However, determining if a string is a palindrome basically costs \(O(\lvert S\rvert)\) time, so it costs a total of \(O(\lvert S\rvert^2)\) time, which will exceed the time limit.

Can we narrow down the candidate of number of a’s to prepend? Here, for a string \(X\), if the \(1\)-st through \(i\)-th character is all a and the \((i+1)\)-th is not, then let’s call \(i\) is “the number of consecutive leading a’s.” (If the \(1\)-st character is not a, we assume \(i=0\).) Let’s also define “the number of consecutive trailing a’s” in the same way. Then, for a string \(T\) that is a palindrome, the number of leading and trailing a’s must be the same.

On the other hand, let \(x\) be the number of consecutive leading a’s, \(y\) be the number of consecutive trailing a’s, and \(S_k\) be \(k\) copies of a’s \((0\leq k)\) succeeded by \(S\). Since \(S\) contains a non-a character, \(S_k\) has \(x+k\) consecutive leading a’s and \(y\) consecutive trailing a’s.

Therefore, if \(x>y\), then we cannot make a no matter how many times we prepend a to \(S\); if \(x\leq y\), \(S_k\) can be a palindrome only if \(k=y-x\), so we only have to inspect \(S_{y-x}\) to check if it is a palindrome.

The values of \(x\) and \(y\) can be found in an \(O(\lvert S\rvert)\) time, and checking whether \((y-x)\) copies of a’s succeeded by \(S\) is a palindrome can be done in an \(O(\lvert S\rvert)\) time too, so the overall time complexity is \(O(\lvert S\rvert)\). Thus, the problem has been solved.

Sample code in 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;
}