[Hackerrank] – Palindrome Index

Question: Given a string, 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.

Input: abckdeedcba
Output: 3 (0 based indexing)

To start off with the problem, we must first understand that there can be two possible ways to make the string a palindrome. If the given string is “bcbc”.

• If we remove the first ‘b’, the string becomes “cbc” which is a palindrome.
• If we remove the last ‘c’, the string becomes “bcb” which is again a palindrome.

Taking a hint from this, we can think of a solution.

1. Take two pointers. Start and end which point at the first and last character of the string.
2. If the characters are same, increase the index of start by 1 and decrease the index of end by 1.
3. If the characters are not same, then we may have to remove one of the characters, i.e. Either the character at start index or the character at end index. This forms 2 substrings:
   – str(0, start-1) + str(start+1, last character)
   – str(0, end-1) + str(end+1, last character)
4. If any of this is a palindrome, we have our result as the start or the end index. If not, then we can simply return -1.

import java.util.Scanner;

// By nikoo28
class PalindromeIndex {

  static boolean isPalindrome(String str) {

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

  static int palindromeIndex(String s) {

    int start = 0;
    int end = s.length() - 1;

    if (isPalindrome(s))
      return -1;

    while (true) {

      if (start > end)
        break;

      if (s.charAt(start) == s.charAt(end)) {
        start++;
        end--;
        continue;
      }

      // Create string after removing start
      if (isPalindrome(s.substring(0, start) + s.substring(start + 1))) {
        return start;
      } else if (isPalindrome(s.substring(0, end) + s.substring(end + 1))) {
        return end;
      } else
        return -1;
    }

    return -1;
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int q = in.nextInt();
    for (int a0 = 0; a0 < q; a0++) {
      String s = in.next();
      int result = palindromeIndex(s);
      System.out.println(result);
    }
  }
}
Code language: Java (java)

You can find the working implementation of the code here.
The problem is also available on Hackerrank.