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 O(N) space and O(N^2) time.