1
\$\begingroup\$

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.

\$\endgroup\$
11
  • 4
    \$\begingroup\$ Would A and C also be acceptable answers for the last test? \$\endgroup\$
    – shiona
    Jan 25, 2014 at 17:02
  • 3
    \$\begingroup\$ Please give an objective winning criterion. \$\endgroup\$
    – Howard
    Jan 25, 2014 at 17:56
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Howard
    Jan 25, 2014 at 17:59
  • 3
    \$\begingroup\$ Why is this tagged "Java"? \$\endgroup\$ Jan 25, 2014 at 18:19
  • \$\begingroup\$ related: codegolf.stackexchange.com/questions/862/… \$\endgroup\$
    – Howard
    Jan 25, 2014 at 18:43

1 Answer 1

0
\$\begingroup\$

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;

    }

}
\$\endgroup\$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.