Competitive Programming: POJ 1159 – Palindrome

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

Link to problem

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 $s$ to get $s_{rev}$ . The solution then is (length of $s$ ) – (length of the LCS of $s$ and $s_{rev}$ ). To obtain a palindrome, we will have to add one character for each character not in the LCS.

1. Define subproblems

Let $D_{ij}$ be the length of the LCS of $x_{1...i}$ and $y_{1...j}$ . NB: subsequence is not the same as substring. A subsequence need not be consecutive, e.g., BCAB is a subsequence of ABCBDAB.

2. Write down the recurrence that relates subproblems

If $x_{i} = y_{j}$ , they both contribute to the LCS:

$D_{ij} = D_{i-1,j-1} + 1$

Otherwise, either $x_{i}$ or $y_{j}$ does not contribute to the LCS, so one can be dropped:

$D_{ij} = max(D_{i-1,j}, D_{i,j-1})$

3. Recognize and solve the base cases

The base cases are: $D_{i0} = D_{0j} = 0$ .

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]);
	}
}