1772 of Caribbean online judge giving a time limit exceeded error. please help me find why is my algorithm taking so long

Question

So I am trying to solve the problem 1772 of the Caribbean online judge web page http://coj.uci.cu/24h/problem.xhtml?abb=1772, the problem asks to find if a substring of a bigger string contains at least one palindrome inside it:

e.g. Analyzing the sub-strings taken from the following string: "baraabarbabartaarabcde"

"bara" contains a palindrome "ara"

"abar" contains a palindrome "aba"

"babar" contains a palindrome "babar"

"taar" contains a palindrome "aa"

"abcde" does not contains any palindrome.

etc etc etc...

I believe my approach is really fast because I am iterating the strings starting at the first char and at the last char at the same time, advancing towards the center of the string looking only for the following patterns: "aa" "aba" whenever I find a pattern like those I can say the substring given contains a palindrome inside it. Now the problem is that the algorithm is taking a long time but I can't spot the problem on it. Please help me find it I am really lost on this one. Here is my algorithm

public static boolean hasPalindromeInside(String str)
{
    int midpoint=(int) Math.ceil((float)str.length()/2.0);
    int k = str.length()-1;

    for(int i = 0; i < midpoint;i++)
    {
        char letterLeft = str.charAt(i);
        char secondLetterLeft=str.charAt(i+1);
        char letterRight = str.charAt(k);
        char secondLetterRight =  str.charAt(k-1);

        if((i+2)<str.length())
        {
            char thirdLetterLeft=str.charAt(i+2);
            char thirdLetterRight=str.charAt(k-2);


            if(letterLeft == thirdLetterLeft || letterRight == thirdLetterRight)
            {
                return true;
            }

        }


        if(letterLeft == secondLetterLeft || letterRight==secondLetterRight)
        {
            return true;
        }

    k--;
    }
    return false;
}
}

I have removed the code that grabs the input strings and intervals of sub-strings, I am using String.substring() to get the substrings and I don't think that will be causing the problem. If you need that code please let me know. Thanks!

Answer 1

I think you can solve this in O(1) time per query given O(n) preprocessing to find the locations of all 2 and 3 character palindromes. (Any even plaindrome will have a 2 character plaindrome at the centre, while any odd will have a 3 character one so it suffices to check 2 and 3.)

For example,

Given your string baraabarbabartaarabcde, first compute an array indicating the locations of the 2 character palindromes:

baraabarbabartaarabcde
000100000000001000000-

Then compute the cumulative sum of this array:

baraabarbabartaarabcde
000100000000001000000-
000111111111112222222-

By doing a subtraction you can immediately work out whether there are any 2 character palindromes in a query range.

Similarly for three character plaindromes:

baraabarbabartaarabcde  String
01001000100000010000--  Indicator
01112222333333344444--  Cumulative