Check if string is a palindrome after removing one character. My working solution is too slow

Question

I cant seem to find a proper solution to an exercise. The exercise asks to create a method that returns true if a string can be a palindrome by removing one character. I have a solution that works but fails tests of large (100,000 character) strings because its exceeding the time limit of 1 second. Can somebody point me in the right direction?

I realize my approach is brute force and I'm sure there's a better way to solve it. I'm assuming my problem lies with the iteration.

public class Main {

    public static boolean makePalindrome(String mjono) {

        StringBuilder sb = new StringBuilder(mjono);


        for (int i = 0; i < mjono.length(); i++) {
            sb.deleteCharAt(i);

            if(isPalindrome(sb.toString())){
                return true;
            } else {
                sb.insert(i, mjono.charAt(i));
            }
        }
        return false;
    }

    private static boolean isPalindrome(String string) {
        return string.equals(new StringBuilder(string).reverse().toString());
    }

    public static void main(String[] args) {
        System.out.println(makePalindrome("ABCBXA"));
        System.out.println(makePalindrome("ABCBAX"));
        System.out.println(makePalindrome("ABCXBA"));
        System.out.println(makePalindrome("ABCDE"));
        System.out.println(makePalindrome("BAAAAC"));
    }
}

These are the tests it fails:

@Test(timeout=1000)
public void suuri2() {
    int n = 100000;
    char[] t = new char[n];
    for (int i = 0; i < n; i++) t[i] = 'A';
    t[12345] = 'B';
    testaaSuuri(new String(t), true);
}

@Test(timeout=1000)
public void suuri3() {
    int n = 100000;
    char[] t = new char[n];
    for (int i = 0; i < n; i++) t[i] = 'A';
    t[12345] = 'B';
    t[54321] = 'C';
    testaaSuuri(new String(t), false);
}

Thanks in advance.

Solution 1

Well, there's of course the naive solution running in O(n ^ 2) by trying each possibility to remove one char.

But we can certainly do better:
We can define a palindrome recursively:

palindrome = x.palindrome.x | x | x.x , where x is an arbitrary token

So how does that help us? Pretty simple: we can derive a rules that allow checking whether the string is palindromic in O(n).

A palindrome consists of a char c, followed by a string that must be empty or palindromic, followed by another c, if it's longer than 1 char. If it's of length 1, it's automatically palindromic.

Thus, the last character must be equal to the first, the second to the second to the last, and so on. So basically:

boolean isPalindrome(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;
}

We have to alter this rule a bit, since once we may remove a single character. This introduces splitting the whole problem into two parts, as we can see from a definition:

palindrome_1 = s.x.palindrome.reverse(s) | s.palindrome.x.reverse(s) | palindrome

As we can easily see, this contains the original palindrome-definition, but in addition allows introduction of one additional char x.

static boolean isPalindrome_1(String s){
    for(int i = 0 ; i < s.length() / 2 ; i++)
        if(s.charAt(i) != s.charAt(s.length() - i - 1))
            return isPalindrome(s , i + 1 , s.length() - i - 1) ||
                    isPalindrome(s , i , s.length() - i - 2);

     return true;
}

static boolean isPalindrome(String s , int lower , int upper){
    while(lower < upper){
        if(s.charAt(lower) != s.charAt(upper))
            return false;

        lower++;
        upper--;
    }

    return true;
}

An explanation/or at least an attempt to explain this:
This piece of code:

if(s.charAt(i) != s.charAt(s.length() - i - 1))
    return isPalindrome(s , i + 1 , s.length() - i - 1) ||
        isPalindrome(s , i , s.length() - i - 2);

Is required, if the definition of palindrome doesn't apply to our input-string. In that case, we have to check two possibilities, how the code was built:

s.x.palindrome.reverse(s)
s.palindrome.x.reverse(s)

If the definition of palindrome doesn't apply, we have reached a point, were we have to ommit either the character of at the start of the remaining string (x.palindrome) or the end of the remaining string (palindrome.x) and see, if the rest matches the definition of a palindrome. This is done by calling isPalindrome(...) with two different substrings, that are cut by one character at either the start or the end of the remaining string.

An few examples of how this code works:

A B C D E F E D C B A
|                   | portion that runs inside isPalindrome_1

A B D E F E D C B A
| |             | |  portion that can be checked inside isPalindrome_1
    |       |        isPalindrome(s , i , s.length() - i - 2)
      |       |      isPalindrome(s , i + 1 , s.length() - i - 1)

As we can see in the second example, the code searched for the first pair of chars that isn't equal. At this point, we have two substrings to search further, which each ommit one character, either at the beginning or the end of the string.

Efficiency:
This code runs in-place - there are never made any copies of the input-string. Runtime is O(n) (O(2 * n) to be precise). Building a faster solution won't be possible - at least until we get quantum computers ;)

Solution 2

Hint 1: since this is an exercise, posting solutions is inappropriate. (It detracts from the learning experience of doing the exercise yourself.)

Hint 2: The following operations are all O(N) for an N character String or StringBuilder:

1. Adding or removing a character from a StringBuilder
2. Creating a new StringBuilder from an existing StringBuilder
3. Reversing a StringBuilder
4. Creating a String from a StringBuilder (toString())
5. Comparing two equal or "almost equal" String objects.

(In most cases you copy or compare N characters. For insertion and deletion, you copy on average 0.5 N characters assuming that the buffer does not need to grow, but that is still O(N). For equals ... it is complicated, but the worst-case is clearly O(N).)

So a fast palindrome tester for large strings needs to avoid these operations.

Hint 3: you can treat the string as an array of characters, either by converting it into a char[] or using charAt(...).

Hint 4: you don't have to physically remove the char from the string. You can just get your algorithm to pretend it isn't there.

Comments

[Rocky]

Thanks for the thorough explanation. I understand the concept, I just need to wrap my head around some of the details.

[Markus]

Please fix your sample solution, it isn't even syntactically valid.

[Paul]

@Markus sry, didn't even test it. I just intended to provide code to show how it works, not to provide a simple copy-and-paste solution. But I'll fix that

[Paul]

@Markus fixed. That was nothing but a few typos and lines I forgot to delete

[Markus]

@Paul Thanks for taking the time. I think code examples posted here should be at least syntactically valid.

[Paul]

@Markus I was in a bit of a hurry, when I posted that yesterday. Sry for the incorrect code :). Anyways, I've the current version of the code is tested. Syntactically correct and results were correct for about a dozen of different input-strings.