Find the Longest Palindrome in a String by Removing Characters

Question

Problem: Remove characters from strings to make the longest (character length) palindrome possible. The first line gives an integer value of the number of strings to test. Each subsequent line is a string to test.

Example Input:

3 // Number of lines to test
GGABZXVYCCDBA
ABGBAD
ABC

Example Output:

ABCCBA
ABGBA
B

Shortest code wins.

Answer 1

Here is my solution in Java (not exactly short hah)...

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class Palindrome {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new File("src/pal.dat"));

        int q = sc.nextInt();
        sc.nextLine();

        for (int z = 0; z < q; z++) {
            String line = sc.nextLine();

            int max = 0;
            String maxP = "";

            for (int k = 0; k < line.length(); k++) {

                String p = calc(line.substring(k));

                if (p.length() > max) {
                    max = p.length();
                    maxP = p;
                }

            }

            System.out.println("Max Palindrome: " + maxP);

        }

    }

    public static String calc(String s) {
        if (s.length() == 0)
            return "";
        if (s.length() == 1 || (s.length() == 2 && s.charAt(0) != s.charAt(1)))
            return s.charAt(0) + "";
        if (s.length() == 2)
            return s;

        char[] arr = s.toCharArray();

        boolean match = false;
        int i = 0;
        for (i = arr.length - 1; i > 0; i--) {
            if (arr[i] == arr[0]) {
                match = true;
                break;
            }
        }

        int max = 0;
        String maxPalin = "";
        for (int k = 1; k < i; k++) {
            String p = calc(s.substring(k, i));
            if (p.length() > max) {
                max = p.length();
                maxPalin = p;
            }
        }

        if (match)
            return arr[0] + maxPalin + arr[0];
        return maxPalin;

    }

}