#include #include #include #include using namespace std; int main() { string s; cin >> s; { string t = s; reverse(t.begin(), t.end()); if(s == t) { cout << "0\n"; return 0; } } vector bad; { int lhs = 0; int rhs = -1 + (int)s.size(); while(lhs < rhs) bad.push_back(s[lhs++] != s[rhs--]); } vector> dp(bad.size() + 1); for(auto& x: dp) x.assign(2, 1e9); // dp[i][0] is the first i are correct, and the next bit is NOT flipped // dp[i][1] is the first i are correct, and the next bit is flipped dp[0][0] = 0; for(int i = 0; i < bad.size(); i++) { // dp[i][0] { // we don't have to do anything! and in fact we should never touch this one if(!bad[i]) { dp[i+1][0] = min(dp[i+1][0], dp[i][0]); } // we can force length two mismatches to always be correct else if(i + 1 == bad.size()) { dp[i+1][0] = min(dp[i+1][0], dp[i][0] + 1); } else { assert(bad[i]); assert(i + 1 < bad.size()); if(bad[i+1]) { // we could keep this one as bad though dp[i+1][0] = min(dp[i+1][0], dp[i][0] + 1); // if the next one is bad, we greedily flip both of them dp[i+2][0] = min(dp[i+2][0], dp[i][0] + 1); } else { // if the next one is good and we flip it, it must be bad dp[i+1][1] = min(dp[i+1][1], dp[i][0] + 1); // we can always make the outer two match with two flips dp[i+2][0] = min(dp[i+2][0], dp[i][0] + 2); } } } // dp[i][1] { if(!bad[i] && i+1 < bad.size()) { assert(!bad[i]); assert(i + 1 < bad.size()); // if the next one is bad, we greedily flip both of them if(bad[i+1]) { dp[i+2][0] = min(dp[i+2][0], dp[i][1] + 1); } else { // if the next one is good and we flip it, it must be bad dp[i+1][1] = min(dp[i+1][1], dp[i][1] + 1); } } } } cout << dp.back()[0] << "\n"; }