How can I convert a string to a palindrome with as few string deletions as possible?
suppose the string is "anuja", the result should be 2, because if I remove the characters "u" and "n", the given string becomes a palindrome. Thus, the output should be as few paragraphs as possible. more examples: input line: "ababa" output: 0 (no delete required) input line: "abcdba" output: 1 (delete "c" or "d") explain the algorithm.
source to share
Let dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome
. We have:
dp[i, i] = 0 for all i (every single character is a palindrome)
To find dp[i, j]
, consider a random string. We have two possibilities:

The first and last characters are equal
a[i] == a[j]
. In this case, we can reduce the problem to finding the minimum number of characters that need to be removed to make the substring a[i+1, j1]
palindrome. 
The first and last characters are not equal:
a[i] != a[j]
. In this case, we need to remove one of them. We will remove whatever leads us to the best solution.
So we have:
dp[i, j] = dp[i + 1, j  1] # if a[i] == a[j]
min(dp[i + 1, j], dp[i, j  1]) + 1 # otherwise
An example of yours anuja
. we'll get:
 1 2 3 4 5

1  0 1 2 2 2
2  0 1 2 3
3  0 1 2
4  0 1
5  0
Note that the matrix is ββcalculated starting at the main diagonal and continuing up, in order, with diagonals parallel to the main diagonal. Answer dp[1, n]
.
This is similar to Levenshtein distance , but it only takes into account distance.
source to share
You can measure the edit distance (levenshtein distance) from a string to its back (ignoring replacements). The desired value will be half that value.
This problem is similar to UVA 10739 . Here's an example.
An example implementation (adapted to your case) could be:
string P, Q;
getline(cin, P);
Q = string(P.rbegin(), P.rend());
int p = P.size(), q = Q.size();
for(int i=0; i<=p; i++) { T[i][0] = i; }
for(int i=0; i<=q; i++) { T[0][i] = i; }
for(int i=1; i<=p; i++) {
for(int j=1; j<=q; j++) {
if (P[i1] == Q[j1])
T[i][j] = T[i1][j1];
else
T[i][j] = min(T[i1][j], T[i][j1]) + 1;
}
}
cout << "Case " << tt << ": " << T[p][q]/2 << endl;
source to share