A good method to solve this problem is to determine the length ~L~ of a longest common subsequence (maximal matching) for the input and its reverse. The answer then is ~N-L~. An alternative approach is to match a prefix of the string with the reverse of a postfix.

The length of a longest common subsequence can be determined by dynamic programming. A triangular table can be constructed, of which only two rows need to be stored. The complexity is then ~\mathcal O(N)~ space and ~\mathcal O(N^2)~ time.

Note that constructing a witness (indicating where which characters have to be inserted to make a palindrome) is computationally more involved and is not asked.