# 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.

+3

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, j-1]`

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.

+12

source

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.

``````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] = i; }
for(int i=0; i<=q; i++) { T[i] = i; }

for(int i=1; i<=p; i++) {
for(int j=1; j<=q; j++) {
if (P[i-1] == Q[j-1])
T[i][j] = T[i-1][j-1];
else
T[i][j] = min(T[i-1][j], T[i][j-1]) + 1;
}
}

cout << "Case " << tt << ": " << T[p][q]/2 << endl;
```

```
0

source

All Articles