3
\$\begingroup\$

I was asked in an interview to write code to check if a given string is a palindrome or can be a palindrome by altering some character without using library function.

My logic is to:

  • Compare 1st char with remaining chars. If it exists, remove both from array using removeElement().
  • If it does not exist in the char array, then use removeFirstElement() to remove the first element 1 time only.
  • chackPotentialPalindrom() returns true if a String can be a palindrome, otherwise false.

package package1;

import java.util.Scanner;

public class Palindrom {
    static int  temp=0;
    static char[] cArr;
        static boolean chackPotentialPalindrom(char[] cAr){
            cArr=cAr;
            if(cArr!=null){
                char current=cArr[0];
                for(int i=1;i<cArr.length;i++){
                    if(current==cArr[i]){
                        cArr=removeElement(i);
                        chackPotentialPalindrom(cArr);
                        break;
                    } 
                    }
                if(cAr.length==2){
                if(cAr[0]==cAr[1]){
                    cArr=null;
                }}
                if(temp==0 && cArr!=null){
                    temp=1;
                    cArr=removeFirstElement(cArr);
                    chackPotentialPalindrom(cArr);
                    }
                }
            if(cArr==null){
                return true;
            }else{
                return false;
            }
        }
        static char[] removeFirstElement(char[] cAr){
            cArr=cAr;
            if(cArr!=null){
            if(cArr.length >1){
            char[] cArrnew=new char[cArr.length-1];
            for(int j=1,k=0;j<cArr.length;j++,k++){
                cArrnew[k]=cArr[j];
            }
            return cArrnew;
            } else {
                return null;
            }
                } else {
                    return null;
                }
        }
        static char[] removeElement(int i){
            if(cArr.length>2){
            char[] cArrnew=new char[cArr.length-2];
            for(int j=1,k=0;j<cArr.length;j++,k++){
                if(i!=j){
                    cArrnew[k]=cArr[j];
                }else{
                    k-=1;
                }
            }
            return cArrnew;}
            else{
                return null;
            }
        }
        public static void main(String[] args) {
            Scanner scn=new Scanner(System.in);
            while(true){
                temp=0;
            String s=scn.next();
            char[] arr=s.toCharArray();
            System.out.println(chackPotentialPalindrom(arr));
            }
        }
    }
  • Any tips to optimize this code?
  • I could not write this in an interview as they have given a pen and paper to code.
  • It took 3 hrs for me to write this. Can I be a developer?
\$\endgroup\$
  • \$\begingroup\$ It would be nice if you could also show example inputs and outputs to illustrate the 'alter some character'... I'm assuming it's to alter a single character...? \$\endgroup\$ – h.j.k. Apr 29 '15 at 8:19
  • \$\begingroup\$ Sure, you can become a developer, but writing code like this on pen and paper should not be that difficult. In this case, for me, the assignment itself is pretty vague and should be more clear. Just give yourself time to gain more experience. small hint: this -> if(cArr==null){ return true; }else{ return false; } can be written as: return cArr==null; \$\endgroup\$ – Stultuske Apr 29 '15 at 8:25
  • \$\begingroup\$ you definitely can be developer \$\endgroup\$ – Panther Apr 29 '15 at 8:26
  • \$\begingroup\$ And while writing code with pen and paper in interview, don't get worried about syntax, if your logic is correct you will get selected. \$\endgroup\$ – Panther Apr 29 '15 at 8:26
  • 1
    \$\begingroup\$ Overcomplicated. All you need is to count occurrence of every character in input string. If length of input string is even, string can be a palindrome if every character occurs even times. If length of input string is odd, there should be one character that occurs odd times. \$\endgroup\$ – Sergey Alaev Apr 29 '15 at 8:42
2
\$\begingroup\$

The above looks to be more work than is necessary. Assuming that we are working with all lower case chars, the following should work.

We match the chars at each end, moving inwards on each cycle. Normally, if any do not match, we consider it a fail and break out. If we are allowed a one pair mismatch (i.e. change one character), then we need to keep track of the count of mismatches and if we have 0 or 1 (less than 2) we consider it to be a palindrome.

private static boolean isAlmostPalindrome(String str){
    int diffCount = 0;
    int left = 0;
    int right = str.length() -1;

    while(right>left){
        if (str.charAt(right--)!= str.charAt(left++)){
            diffCount++;
        }
    }
    return diffCount <2;
}
\$\endgroup\$
  • \$\begingroup\$ Until we get a better clarification from OP about this 'alternation' rule, I still think this suggestion is potentially flawed: abcbe will return true for your method, but the desired output may be false if we assume that the character e can't be 'altered' with any other characters within the input... that's the clarification we need. :) \$\endgroup\$ – h.j.k. Apr 29 '15 at 8:50
  • \$\begingroup\$ @h.j.k. abcde was one of the test cases that I used and it returns false. a/e, b/d both mis-match thus we have a count of 2 and a false result. Some clarification on the reqs is always good :) but I would interpret 'altering a character' as changing the value for it whereas swapping two characters would count as altering two characters. \$\endgroup\$ – AlanT Apr 29 '15 at 9:04
  • \$\begingroup\$ I typed abcbe ;) \$\endgroup\$ – h.j.k. Apr 29 '15 at 9:05
  • 1
    \$\begingroup\$ @h.j.k. my bad! We are back to the reqs. If altering means change the value, then true is correct. change the e to an a. If altering means swap with another then it should be false as no arrangement of abbce can ever be a palindrome. \$\endgroup\$ – AlanT Apr 29 '15 at 9:16
  • \$\begingroup\$ Question is not only to check for palindrome. \$\endgroup\$ – Abhishek Apr 30 '15 at 4:56
2
\$\begingroup\$

Why not count all occurrences of the letters? Also count the string length.

  1. If the string length is even and all characters occur even number of times, then it is a palindrome.
  2. If the string length is odd and all characters occur even number of times except for one character that occurs odd number of times, then it is a palindrome.
  3. Otherwise, it is not.
\$\endgroup\$
  • \$\begingroup\$ This is not an accurate way of finding a palindrome. According to your method, "aabb" is a palindrome, and so is "aabbc". \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Apr 29 '15 at 19:23
  • \$\begingroup\$ @Hosch250 look at clarifying comments on question. It is allowed to change order of characters, so the answer is correct. \$\endgroup\$ – Łukasz Ciosek Apr 29 '15 at 19:49
  • \$\begingroup\$ @ŁukaszCiosek OK, thanks for the comment. \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Apr 29 '15 at 19:50
  • \$\begingroup\$ This approach will work fine but I think it will take same effort as mine ,as we are we have to write without using library function. \$\endgroup\$ – Abhishek Apr 30 '15 at 4:37
1
\$\begingroup\$

For every character in the string, check if the occurrence of that character in the string is an even number. Repeat this for every character and we can tolerate a maximum of 1 odd number. It's funny how people tend to over-think simple situation like this.

\$\endgroup\$
  • \$\begingroup\$ "can be a palindrome by altering some characters". Read the details, that's what make you a good programmer :) Edit: AACCB can be altered to become a palindrome : ACBCA \$\endgroup\$ – Mc Kevin Apr 29 '15 at 8:46
  • \$\begingroup\$ I think years of being confronted with adverts, bylines and people-who-shout-all-the-time mean I now never read anything in bold or upper case! I retract my complaint! Sorry. \$\endgroup\$ – bye Apr 29 '15 at 8:49
  • \$\begingroup\$ yeah, just throught we were looking for comparison, I'm only up at this insane time because I'm really congested, probably time to go back to bed.... \$\endgroup\$ – Scott Sosna Apr 29 '15 at 8:51
1
\$\begingroup\$

The logic here is to find a character and its number of occurrence then check if that has more than one odd number of characters exist. If so, then the string cannot be a palindrome, else it will be a palindrome. I checked with few complex inputs and it worked fine. If the method returns "YES" then it could be altered and can be palindrome, if not, then "NO".

 static String got(String password) {
    HashMap<Character, Integer> checkpass = new HashMap<>();
    Character ch = null;
    Integer val = 0;
    int odd = 0, even = 0;
    for (int i = 0; i < password.length(); i++) {
        ch = password.charAt(i);
        if (checkpass.containsKey(ch) == false) {
            checkpass.put(ch, 1);
        } else {
            val = (Integer) checkpass.get(ch);
            checkpass.put(ch, val + 1);
        }
    }
    Set<Character> hashval = checkpass.keySet();
    for (Character key : hashval) {
        val = (Integer) checkpass.get(key);
        if (val == password.length())
            return "YES";
        else if (val % 2 == 1)
            odd++;
        else
            even++;
    }
    if (odd == 1 || odd == 0)
        return "YES";
    else
        return "NO";
}
\$\endgroup\$
  • \$\begingroup\$ This code will work perfectly fine but you are using library function in this. \$\endgroup\$ – Abhishek Jul 25 '15 at 11:00
-1
\$\begingroup\$

It's late and I'm not really awake, but should be able to do it by processing array elements together. For odd length strings, the middle element is obviously equals and I believe this skips it.

boolean success = true;
char[] array = stringToCheck.toCharArray();
int length = stringToCheck.length();
int halfLength = (int) length / 2;

for (int i = 0; sucess && i < halfLength; i++) {
   success = (array[i] == array[length - 1 - i]);
}

System.out.println ("Palindrome=" + success);

So much simpler than you were making it out to be.

\$\endgroup\$
  • \$\begingroup\$ Here the question is not only checking whether the string is palindrome, but also to check whether any alteration made to strings (swaps) could make it palindrome. Eg, acdfcda, swapping 5,6 characters make this palindrome and should return true, if I am not wrong \$\endgroup\$ – HJK Apr 29 '15 at 8:34

protected by Jamal Sep 15 '18 at 5:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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