Make a given string as palindrome using java

Question

Can anyone please help me to solve below problem

Check whether the string is palindrome or not. If the string is not palindrome then make it palindrome.

eg: input: ABC, output: ABCBA

I know how to check whether string is palindrome or not. Please help in the second part of the question.

in best case, better if we can achieve below result also

eg: input: AAB, output: ABA

for 1st exmaple i tried this approach

 LinkedList <String> q = new LinkedList<>();
    //String [] ar ={"a","b","c","b","d"};
    String [] ar ={"A","B","C"};;
    int mid=ar.length/2;

    q.addFirst(ar[mid]);
    for(int i= mid, j=mid; i>=0&&j<ar.length;){
        if(j+1==ar.length && i-1==-1)
            break;
        q.addFirst(ar[i-1]);
        if(ar[i-1]!=ar[j+1]){
            q.addLast(ar[i-1]);
            q.addLast(ar[j+1]);
            q.addFirst(ar[j+1]);

        }else{
            q.addLast(ar[j+1]);
        }
        j++;
        i--;
    }

Why can we take AAB and make ABA? Could we take ABC and make ABA? Or even the truly ideal {'A','B','C'} which is three one character palindromes? — Elliott Frisch, Nov 23 '14 at 18:52
You have to show us some sort of effort in solving the problem. StackOverflow isn't a 'code-order' website. [What have you tried](http://www.whathaveyoutried.com)? What possible solutions do you think there are? Have you tried looking around for this answer anywhere else? — Alex K, Nov 23 '14 at 18:54
@Elliott Frisch: no second one is a different example. It is not related to the first one. In first example we are just adding the part of string to the original (no deletion of existing chars). Where as in second one I am thinking we can make use of repeated words (to make minimum insertion), instead of making AAB--> AABAA, better we can do ABA — Babulu, Nov 23 '14 at 18:56
What transformation of the input string are allowed? It is not clear why AAB can become ABA. — kraskevich, Nov 23 '14 at 18:58
@Alex, I have searched in stack overflow and tried [this](http://stackoverflow.com/questions/2237021/how-can-i-compute-the-number-of-characters-required-to-turn-a-string-into-a-pali). But I am not able to understand the approach suggested. I have tried using linkedlist for the example 1. Couldn't able to do for example 2 — Babulu, Nov 23 '14 at 18:59
@user2040251: In order to make a string as palindrome with minimal insertion of new character, why can't we just use which are repeated more than once — Babulu, Nov 23 '14 at 19:02
But there is no insertion here at all. It is swapping two characters. I think you need to formalize the rules of input transformation to make this question answerable. — kraskevich, Nov 23 '14 at 19:06
yes.. it is swapping. Apologies for using wrong terminology. — Babulu, Nov 23 '14 at 19:10
I was afraid to post my code, getting of many kick backs from the community. I have posted my code for your information, even i think it is really a poor one. I am a beginner for coding, so please encourage. — Babulu, Nov 23 '14 at 19:24

score 1 · Accepted Answer · answered Nov 24 '14 at 10:26

Answering my own question. For second example

public static boolean makePal(String input){

    HashMap<Character, Integer> map = new HashMap<>();
    int value =1, numberOfOddOccurence = 0;
    //find the number of occurrences
    for(int i=0; i<input.length(); i++){
        char key = input.charAt(i);
        if(!map.containsKey(key)){
            map.put(key, value);
        }else{
            map.put(key, map.get(key)+1);
        }
    }

    //find the number of char with odd counts
    for(Map.Entry<Character, Integer> a : map.entrySet()){
        if(a.getValue()%2==1){
            numberOfOddOccurence++;
        }
    }

    if(numberOfOddOccurence>1)
        return false;
    else{
        char [] charArray = new char[input.length()];
        int cursor = 0;
        for(Map.Entry<Character, Integer> a : map.entrySet()){
            if(a.getValue()%2==0){
                charArray[cursor] = (char)(a.getKey());
                charArray[input.length()-cursor-1] = (char)(a.getKey());
                cursor++;
            }else{
                charArray[(int) Math.ceil(input.length()/2)] = (char) (a.getKey());
            }
        }
        System.out.println(String.valueOf(charArray));
    }

    return true;
}

Make a given string as palindrome using java

1 Answers1