Find the Longest Palindrome in a String by Removing Characters [duplicate]

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
ABC

Example Output:

ABCCBA
ABGBA
B

Shortest code wins.

• Would A and C also be acceptable answers for the last test? Jan 25 '14 at 17:02
• Please give an objective winning criterion. Jan 25 '14 at 17:56
• From your example I infer that you ask for a complete program which can process multiple strings as input. The problem specification only asks for a single string - can you please clarify. Also does largest means longest/most characters? Jan 25 '14 at 17:59
• Why is this tagged "Java"? Jan 25 '14 at 18:19
• Jan 25 '14 at 18:43

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) {
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 + maxPalin + arr;
return maxPalin;

}

}