Optimize Palindrome Index HackerRank Solution

Palindrome Index optimized Java solution

Photo by Dell on Unsplash

HackerRank Palindrome Index is a basic problem but hard to pass all test cases. Here will illustrate how to solve and optimize in Java, which can be easy to understand and extend to other problems.

Problem

Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome. There may be more than one solution, but any will do. If the word is already a palindrome or there is no solution, return -1. Otherwise, return the index of a character to remove.

Example

s = "bcbc"

Either remove ‘b’ at index 0 or ‘c’ at index 3.

Function Description

Complete the palindromeIndex function in the editor below.

palindromeIndex has the following parameter(s):

• string s: a string to analyze

Returns

• int: the index of the character to remove or -1

Below is HackerRank problem statement:

Palindrome Index | HackerRank

Optimized Solution

It’d be straightforward to implement using a loop to check if the substring is a palindrome or not. The time complexity is O(n²). But it would fail in many HackerRank test cases.

In Java, it can be optimized in two ways: 1. operate on a char array after converting from the string since Java String is immutable; 2. check the char array from two ends to speed up. Please see the optimized Java solution below.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'palindromeIndex' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int palindromeIndex(String s) {
        // Write your code here
        if (s == null || s.length() < 2) return -1;
        char [] ss = s.toCharArray();
        int l = 0, r = ss.length - 1;
        
        if (isPal(ss, l, r)) return -1;
        while (l < r) {
            if (isPal(ss, l+1, r)) return l;
            if (isPal(ss, l, r-1)) return r;
            if (ss[l] != ss[r]) return -1;
            l++;
            r--;
        }
        
        return -1;
    }
    
    static boolean isPal(char [] s, int l, int r) {
        if (s == null || l > r) return false;
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        
        return true;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String s = bufferedReader.readLine();

                int result = Result.palindromeIndex(s);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Please see the test result below.

But it still fails in one special test case. If you do HackerRank Mock Test, you will fail its 15th test case. Let’s optimize or simplify it further as follows.

class Result {
    /*
     * Complete the 'palindromeIndex' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */
  public static int palindromeIndex(String s) {
        // Write your code here
        if (s == null || s.length() < 2) return -1;
        char [] ss = s.toCharArray();
        int l = 0, r = ss.length - 1;
        if (isPal(ss, l, r)) return -1;
        while (l < r) {
            if (ss[l] != ss[r]) {
                if (isPal(ss, l+1, r)) return l;
                if (isPal(ss, l, r-1)) return r;
            } 
            l++; 
            r--;
         }

         return -1; 
    }

    static boolean isPal(char [] s, int l, int r) {
        if (s == null || l > r) return false;
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
}

That’s it. Assume there may be a palindrome and keep the loop running. The above solution can pass the hard mock test. Please see below.

Happy coding!

Questions, ideas? Leave comments in Respond below. Connect with me to be part of the journey to solve interesting problems.