Finding the index of the character whose removal will make a palindrome

Question

Before I get into describing by problem I'd like to point out I found this question under c++ tag. But the solution of that question is already implemented in my code.

I am solving a problem from hackerrank. My code for that problem is logically correct but in some of the cases time limit exceeds.

Problem Statement

Given a string S , of lowercase letters, determine the index of the character whose removal will make a S palindrome. If is already a palindrome or no such character exists, then print -1 . There will always be a valid solution, and any correct answer is acceptable. For example, if S = "bcbc", we can either remove 'b' at index 0 or 'c' at index 3.

Input Format:

The first line contains an integer T , denoting the number of test cases.

Each line i of the T subsequent lines describes a test case in the form of a single string, Si.

Constraints:

Length of the string can be 100005.

Output Format:

Print an integer denoting the zero-indexed position of the character that makes S not a palindrome; if S is already a palindrome or no such character exists, print -1 .

As a solution my code is as following:

import java.io.*;
import java.util.*;

public class Solution {

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

    return true;
}

public static void main(String[] args) throws IOException{
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int t = Integer.parseInt(br.readLine());
    while(t-->0){
        int flag = 0;
        String sb = br.readLine().toString();
        if(isPalindrom(sb)){
            System.out.println("-1");
            flag = 1;
        }
        for(int i=0;i<sb.length()&&flag==0;i++){
            StringBuffer s = new StringBuffer(sb);
            s.deleteCharAt(i);
            if(isPalindrom(s.toString())){
                System.out.println(i);
                break;
            }   
        }
        
    }
}}

I've used best palindrome checker algorithm as described here. and also used BufferedReader as described here. But time limit exceeds in some taste cases. How can I improve my code further?

Thanks in advance!

Answer 1

Import on demand

Instead of import java.io.*; it is advised to explicitly list all the classes you use:

import java.io.SomeClass1;
import java.net.SomeClass2;
// And so on...

IO facilities

Instead of

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

you could have used

Scanner scanner = new Scanner(System.in);

It's so much easier to use Scanner (try it!)

Performance

for(int i=0;i<sb.length()&&flag==0;i++){
    StringBuffer s = new StringBuffer(sb);
    s.deleteCharAt(i);
    if(isPalindrom(s.toString())){
        System.out.println(i);
        break;
    }   
}

The above is a show-stopper: you keep populating an entire string builder for each index of the char to ignore; see below for a faster implementation.

API

It would be so much better, if you dedicated a (static) method for running the entire algorithm; again, see below.

Summa summarum

All in all, I had this in mind:

import java.util.Scanner;
import java.util.stream.IntStream;

public class Solution {

    public static int isOnePastPalindrome(final String s) {
        final int stringLength = s.length();

        for (int indexOfIgnoredCharacter = -1;
                indexOfIgnoredCharacter < stringLength;
                indexOfIgnoredCharacter++) {
            if (isOnePastPalindrome(s, indexOfIgnoredCharacter)) {
                return indexOfIgnoredCharacter;
            }
        }

        return -1;
    }

    private static boolean isOnePastPalindrome(final String s, 
                                               final int ignoreIndex) {
        int leftIndex = 0;
        int rightIndex = s.length() - 1;

        while (leftIndex < rightIndex) {
            if (leftIndex == ignoreIndex) {
                // Just omit the character at index leftIndex (which is the same
                // as ignoreIndex).
                leftIndex++;
            } else if (rightIndex == ignoreIndex) {
                // Same fro the right index.
                rightIndex--;
            } else {
                if (s.charAt(leftIndex) != s.charAt(rightIndex)) {
                    // Mismatch. Removing the character at index 'ignoreIndex'
                    // will not make this string a palindrome.
                    return false;
                }

                leftIndex++;
                rightIndex--;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = Integer.parseInt(scanner.nextLine().trim());

        IntStream.range(0, testCases).forEach((i) -> {
            System.out.println(
                    isOnePastPalindrome(
                            scanner.nextLine().trim().toLowerCase()));
        });
    }
}

Hope that helps.

P.S.

Note that we do not need a dedicated method for (pre)checking that an input string is a palindrome; just call isOnePastPalindrome with ignoreIndex set to a negative value.

Answer 2

Code Style

As @coderodde also remarked, you should import specific classes. Wildcard imports are for throw-away code and early development; no later than when your code is approaching completeness, you should replace any then-remaining wildcard imports with specific imports. There are tools that can help you with that.

Also, format your code consistently. Your indentation and placement of spaces are irregular. I find code much easier to read when there are spaces on each side of every binary operator, but if you prefer not to use such spaces then at least be consistent!

I/O

For what it's worth, unlike @coderodde, I have no problem with BufferedReader for your input. For input whose form is so simple, Scanner does not provide much advantage.

Performance

This is the main area of concern, and indeed I do not find it surprising that your code ...

        for(int i=0;i<sb.length()&&flag==0;i++){
            StringBuffer s = new StringBuffer(sb);
            s.deleteCharAt(i);
            if(isPalindrom(s.toString())){
                System.out.println(i);
                break;
            }   
        }

... does not perform well. Regardless of the details of the palindrome-checking algorithm, it is performing far more work than it needs to do when used this way. In particular, it is very wasteful to test every deletion candidate, and it is slightly wasteful to test separately whether the full string is already a palindrome. For each string it tests, your code may perform work proportional to the square of the length of the string.

Instead of testing every possible deletion, simply scan each test string from both ends until you find a pair of corresponding characters that differ. If the string can be made a palindrome by deleting a single character, then that character will be one of those two. They are the only candidates you need to consider. By limiting yourself to considering only those as deletion candidates, the maximum amount work performed by your code is only linear in the length of the string. (Also, if every corresponding pair of characters matches, then the string is already a palindrome, so you don't need to perform a separate check for that.)