создать функцию, которая возвращает строки массива, переставленные в виде палиндрома

Я думаю, вам следует разделить свое решение на два отдельных случая: нечетный случай и четный случай. В обоих случаях сделайте массив подсчета частотных символов.

 First Case:
    1) Check that all chars have even count but one.
    2) Create a stringBuffer and append the odd char and decrement its count
    3) For each of the remaining characters form your palindrome by adding a char at the front and a char at the end of the string buffer.

 Second Case:
    1) Check that all chars have even counts.
    2) Create a string buffer
    3) For each of the remaining characters from your palindrome as case one.

Для каждого String превратите его в отсортированный List или массив символов. Затем пройдитесь по списку символ за символом, подсчитывая количество вхождений каждого символа. Если число (n) нечетное, вставьте n вхождений вашего символа в середину вывода String. Если n четно, поставьте n/2 в начале вывода String и n/2 в конце. Если вы встретите более двух символов с нечетным числом вхождений, вы должны вернуть -1. Когда вы дойдете до конца списка, поместите вывод String в выходной массив. И если вы пройдете весь путь, верните этот массив.

public static Object build(String[] arrayOfStrings) {
    String[] palindrome = new String[arrayOfStrings.length];

    for (int i = 0; i < arrayOfStrings.length; i++) {
    String currentString = arrayOfStrings[i];
    if (currentString.isEmpty()) {
        palindrome[i] = currentString;
    } else {
        char[] chars = Arrays.copyOf(currentString.toCharArray(),
            currentString.length() + 1);
        chars[currentString.length()] = Character.MAX_VALUE;
        Arrays.parallelSort(chars);

        char currentChar = chars[0];
        int count = 1;
        boolean foundOdd = false;
        String newString = "";
        for (int j = 1; j < chars.length; j++) {
            if (chars[j] == currentChar) {
                count++;
            } else {
                if (foundOdd) {
                    if (count % 2 == 0) {
                        newString = even(newString, currentChar, count);
                    } else {
                        return -1;
                    }
                } else {
                    if (count % 2 == 0) {
                        newString = even(newString, currentChar, count);
                    } else {
                        foundOdd = true;
                        newString = odd(newString, currentChar, count);
                    }
                }
                count = 1;
                currentChar = chars[j];
            }
        }
        palindrome[i] = newString;
        newString = "";
        }
    }
    return palindrome;
}

private static String even(String oldString, char currentChar, int count) {
    assert count % 2 == 0;
    int halfCount = count / 2;
    String occurrences = "";
    for (int i = 0; i < halfCount; i++) {
        occurrences += currentChar;
    }
    return occurrences + oldString + occurrences;
}

private static String odd(String oldString, char currentChar, int count) {
    assert count % 2 == 1;
    int length = oldString.length() / 2;
    String occurrences = "";
    for (int i = 0; i < count; i++) {
        occurrences += currentChar;
    }
    return oldString.substring(0, length) + occurrences
        + oldString.substring(length);
}

// code from main function calling above function is:
public static void main(String[] args) {
    String a[] = { "abb", "aaaabbcccddddeeffgghhii" };
    Object result = build(a);
    if (result.equals(-1)) {
        System.out.println("Failed to find a palindrome for at least one of the input values");
    } else {
        String[] resultStr = (String[]) result;
        for (int i = 0; i < resultStr.length; i++) {
            System.out.println(resultStr[i]);
        }
    }
}

Код выше ужасен. С одной стороны, он сильно опирается на String конкатенацию. Но это работает.