Hackerrank - Solving Palindrom Index Solution

Question

Problem:

Given a string of lower case letters in the range ascii[a-z], identify the index of character to be removed to change the string into a palindrome. If the string cannot be converted to palindrome or is already a palindrome just return -1 else return index of the character to be removed.

My Solution:

public static int palindromeIndex(String s) {

    if(p(s)){
        return -1;
    }

    StringBuilder sb = new StringBuilder(s);

    for(int i=0; i<s.length(); i++){

        sb.deleteCharAt(i);
        if(p(sb.toString())){
            return i;
        }
        sb.insert(i,s.charAt(i));
    }


    return -1;

}

private static boolean p(String s){

    for(int i=0; i<s.length()/2; i++){
        if(s.charAt(i) != s.charAt(s.length() - i - 1)){
            return false;
        }
    }

    return true;
}

It is failing for one or all below test cases (unable to determine for which one) according to hackerrank:

1. quyjjdcgsvvsgcdjjyq
2. hgygsvlfwcwnswtuhmyaljkqlqjjqlqkjlaymhutwsnwcflvsgygh
3. fgnfnidynhxebxxxfmxixhsruldhsaobhlcggchboashdlurshxixmfxxxbexhnydinfngf
4. bsyhvwfuesumsehmytqioswvpcbxyolapfywdxeacyuruybhbwxjmrrmjxwbhbyuruycaexdwyfpaloyxbcpwsoiqtymhesmuseufwvhysb
5. fvyqxqxynewuebtcuqdwyetyqqisappmunmnldmkttkmdlnmnumppasiqyteywdquctbeuwenyxqxqyvf
6. mmbiefhflbeckaecprwfgmqlydfroxrblulpasumubqhhbvlqpixvvxipqlvbhqbumusaplulbrxorfdylqmgfwrpceakceblfhfeibmm
7. tpqknkmbgasitnwqrqasvolmevkasccsakvemlosaqrqwntisagbmknkqpt
8. lhrxvssvxrhl
9. prcoitfiptvcxrvoalqmfpnqyhrubxspplrftomfehbbhefmotfrlppsxburhyqnpfmqlaorxcvtpiftiocrp
10. kjowoemiduaaxasnqghxbxkiccikxbxhgqnsaxaaudimeowojk

My Output:

1. 1
2. 8
3. 33
4. 23
5. 24
6. 43
7. 20
8. -1
9. 14
10. -1

I debugged to code locally, and according to my understanding, this test case is working fine. Please help me out understating, what is wrong with the code.

Note: I can do it with other alternative ways (more simpler ways), solutions are available online, but i am trying to understand, what is wrong with my piece of java code. Thanks.

Answer 1

Your code times out on some test cases. It is not very efficient to try to delete each character and then check whether that is a palindrome.

By first checking whether the original string is a palindrome you can find the spot where it fails, which leaves you with just 2 possibilities for deletion. So you would only need to try those two. Moreover, you don't actually have to perform the deletion. You can just skip the concerned character and continue the palindrome check by skipping the corresponding index.

Here is a possible implementation:

    public static int palindromeIndex(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end && s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        if (start >= end) return -1; // already a palindrome
        // We need to delete here
        if (isPalindrome(s, start + 1, end)) return start;
        if (isPalindrome(s, start, end - 1)) return end;
        return -1;
    }

    public static boolean isPalindrome(String s, int start, int end) {
        while (start < end && s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        return start >= end;        
    }