Playing with Palindromes - Part 1

Today I'll show some problems involving palindromes:

The first problem is stated as followed: "Given a string S, return the minimum number of characters required to be deleted from S, in order to turn it into a Palindrome".

By definition, the minimum characters solution will give us also the maximal size palindrome, but lets focus first on the minimum.

Lets define the problem as P(N) - the minimum number of characters required to be deleted to create a palindrome from string S of size N. if S is a palindrome, then the answer should be 0. if S has all unique characters, then the answer should be N - 1 (since a string of size 1 is a palindrome). Lets assume that we know how to solve this problem for any string n < N. How can we solve P(N + 1) ? there are two options here: the first is to think how we can extend the solution from n < N to N + 1. The second is to think how we can reduce N + 1 to n < N. in this case the second option will be easier. consider the N+1'th character of S. it either participates in the palindrome or it doesn't. It can participate in the palindrome in two cases: the first, it is equal to the first character of S, in which case we need to see what P(N - 2) is equal to. In the second case, it can participate in a palindrome that starts at the second character of S for example S = BS'A |S| = N + 1, and S' = AS'' , |S'| = N - 2. In this case we need to check P(N - 1) and add 1 to its result (since we decided to delete the first character of S). The last option is that the N+1'th character is not present in the solution, so we need to delete it. In this case we need to check again P(N - 1) and add 1 to it (since we are about to delete the N + 1'th character of S). 

Notice that our problem definition in terms of just N is not very robust. Instead of defining the problem in terms of just N,let adds an additional parameter: the beginning of the string.

P(i,n < N) - we know how to find the minimal number of character deletions for any sub string of S starting at index i and of size n < N.

Base case: P(i,1) = 0

P(i,N) = MIN{S[i] == S[i + N - 1] ? P(i + 1, N - 2) : INFINITY ,P(i + 1,N - 1) + 1, P(i,N - 1) + 1}

The above equation is merely a formalization of what we spoke about in the paragraph above (using the ternary operator).

How does the code look like for this:

In such a problem in which there is the optimal substructure property, dynamic programming is called for.

The run time complexity of this code is O(N^2). 

I'll come back with some additional problems related palindromes soon enough.