/**
* Calculate the minimal number of letters one should add to a given string to make it a palindrome.
* INPUT:
* A string.
* OUTPUT:
* The minimal number of letters we should insert to the string to make it a palindrome.
* ALGORITHM:
* - Loop over all characters s[i].
* - Assume that s[i] is the center of the palindrome.
* - (if s[i]==s[i+1], assume that s[i,i+1] are the center).
* - Calculate the edit distance between the two sides of s[i].
* - Return the minimum edit distance.
*
* @author Erel Segal
* @date 2010-11-02
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
template <class T> class matrix {
protected:
uint myRows, myCols;
vector<T> myData;
public:
matrix<T> () {}
matrix<T> (uint rows, uint cols):
myRows(rows), myCols(cols),
myData(rows*cols) {}
void resize (int rows, int cols) {
myRows=rows; myCols=cols;
myData.resize(rows*cols);
}
T& at(uint row, uint col) { return myData[row*myCols+col]; }
const T& at(uint row, uint col) const { return myData[row*myCols+col]; }
void fill (T value) { ::fill(myData.begin(), myData.end(), value); }
void print(ostream& out) const {
for (uint row=0; row<myRows; ++row) {
const T* temp = &myData[row*myCols];
for (uint col=0; col<myCols; ++col) {
out << temp[col] << " ";
}
out << endl;
}
}
friend ostream& operator<< (ostream& out, const matrix<T>& m) { m.print(out); return out; }
};
/** Compute the longest common subsequence between X and Y
* On return, C will contain the LCS table.
* @return C[m][n], that is the length of the longest common subsequence.
* @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
* @see http://e...content-available-to-author-only...a.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems
*/
template<typename Iterator> size_t editDistance(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
size_t m = std::distance(X, Xend);
size_t n = std::distance(Y, Yend);
matrix<size_t> C(m+1, n+1);
// Initialize the zeroth row and zeroth column:
for (size_t i=0; i<=m; ++i)
C.at(i,0) = 0;
for (size_t j=0; j<=n; ++j)
C.at(0,j) = 0;
for (size_t i=0; i<m; ++i)
for (size_t j=0; j<n; ++j)
if (X[i] == Y[j])
C.at(i+1,j+1) = C.at(i,j) + 1;
else
C.at(i+1,j+1) = std::max(C.at(i+1,j), C.at(i,j+1));
size_t LCSLength = C.at(m,n);
return m+n-2*LCSLength;
}
void minimizePalindromizationCost(size_t& minimumCost, const string& forward, const string& backward, size_t length, size_t centerPosition) {
//cout << "center=" << centerPosition << " ";
if (centerPosition>=length)
return;
if (centerPosition>0 && forward[centerPosition]==forward[centerPosition-1])
return; // a substring of identical letters is checked when it starts.
char centerLetter = forward[centerPosition];
size_t centerLength=1; // The number of letters identical to centerLetter
++centerPosition;
while (centerPosition<length && forward[centerPosition]==centerLetter) {
++centerLength;
++centerPosition;
}
//cout << centerPosition << ":" << centerLength << ":";
size_t lengthForward = centerPosition-centerLength;
size_t lengthBackward = length-centerPosition;
if ((size_t)abs((int)lengthForward-(int)lengthBackward)>=minimumCost)
return; // the edit distance cannot be smaller!
size_t currentCost = editDistance(
forward.begin(), forward.begin()+lengthForward,
backward.begin(), backward.begin()+lengthBackward);
//cout << currentCost << endl;
if (currentCost<minimumCost)
minimumCost = currentCost;
}
size_t palindromizationCost(const string& forward) {
size_t length = forward.size();
size_t middle = length/2; // TODO: start with the middle to save cost
string backward=forward;
reverse(backward.begin(), backward.end());
size_t minimumCost = length-1;
size_t centerPosition;
for (size_t radius=0; radius<=length/2; ++radius) {
//cout << "radius=" << radius << " ";
centerPosition = middle+radius;
if (centerPosition<length)
minimizePalindromizationCost(minimumCost, forward, backward, length, centerPosition);
if (radius==0) continue; // check the other direction only when radius>0
centerPosition = middle-radius;
minimizePalindromizationCost(minimumCost, forward, backward, length, centerPosition);
}
return minimumCost;
}
void assertCost(string s, size_t expected) {
time_t before = time(NULL);
size_t a = palindromizationCost(s);
if (a!=expected) {
cerr << "ERROR: Cost of " << s << " should be " << expected << " but was " << a << endl;
} else {
time_t after = time(NULL);
cout << "calculated cost of " << s.size() << " chars in " << (after-before) << " seconds" << endl;
}
}
void testIdentical(int N) {
string s(N, 'b');
assertCost(s,0);
}
void testHalf(int N) {
N += (N%2); // make N even
string s(N, 'b');
for (int i=0; i<N/2; ++i) {
s[i] = 'a';
}
assertCost(s,N/2);
}
void testAlternating(int N) {
N += (N%2); // make N even
string s(N, 'b');
for (int i=0; i<N; i+=2) {
s[i] = 'a';
}
assertCost(s,1);
}
void testStart(int N) {
string s(N, 'b');
s[0] = 'a';
assertCost(s,N>1? 1: 0);
}
void testStartEnd(int N) {
string s(N, 'b');
s[0] = 'a';
s[N-1] = 'c';
assertCost(s, N>2? 2: N==2? 1: 0);
}
void testStartEndIdentical(int N) {
string s(N, 'b');
s[0] = 'a';
s[N-1] = 'a';
assertCost(s,0);
}
void testDifferent(int N) {
string s(N, 'a');
for (int i=0; i<N; i++) {
s[i] = (i%256);
}
assertCost(s,N-1);
}
int main() {
size_t N;
cin >> N; // length of string
/* tests:
assertCost("Ab3bd",2);
testIdentical(N);
testHalf(N);
testAlternating(N);
testStart(N);
testStartEnd(N);
testStartEndIdentical(N);
testDifferent(N);
*/
string s;
cin >> s;
cout << palindromizationCost(s) << endl;
}