### Description

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome.

### Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.

### Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

### Sample Input

5 Ab3bd

### Sample Output

2

Solution below . . .

### Steps for Solving Dynamic Programming Problems

This is a dynamic programming problem but it’s an interval DP problem, which means that the solution is not found in a linear, bottom-up way. Since I’ve already solved it, I know that we’re going to have to tweak the generic DP algorithm in a way that the interval DP algorithm is not easy to tweak, so we’ll convert this to a Longest Common Subsequence (LCS) problem, a 2-dimensional DP problem that ** is** easy to tweak.

What we’re going to do is reverse the input string to get . The solution then is (length of ) – (length of the LCS of and ). To obtain a palindrome, we will have to add one character for each character not in the LCS.

**1. Define subproblems**

Let be the length of the LCS of and . **NB:** *subsequence* is not the same as *substring*. A subsequence need not be consecutive, e.g.,

**2. Write down the recurrence that relates subproblems**

If , they both contribute to the LCS:

Otherwise, either or does not contribute to the LCS, so one can be dropped:

**3. Recognize and solve the base cases**

The base cases are: .

So far, so good, but if we implement and submit the algorithm described above, we get a **Memory Limit Exceeded** error. The input string can be up to 5,000 characters so the DP matrix alone can be up to 25MB.

Fortunately, we calculate the matrix values one row at a time, based only on the values of the previous row. So we really only need to maintain 2 rows at a time, not 5,000.

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String s = sc.next(); sc.close(); StringBuilder sb = new StringBuilder(s); String rev = sb.reverse().toString(); int a = s.length(); int b = rev.length(); int[] dpPrev = new int[b + 1]; int[] dpCurr = new int[b + 1]; for (int i = 0; i <= b; i++) dpPrev[i] = 0; for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { if (s.charAt(i - 1) == rev.charAt(j - 1)) dpCurr[j] = dpPrev[j - 1] + 1; else dpCurr[j] = Math.max(dpPrev[j], dpCurr[j - 1]); } dpPrev = Arrays.copyOf(dpCurr, dpCurr.length); dpCurr = new int[b + 1]; dpCurr[0] = 0; } System.out.println(N - dpPrev[b]); } }