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.

Seems to be a popular question, see http://stackoverflow.com/questions/10577422/create-palindrome-from-existing-string-by-removing-characters?s=3|0.8945 — Frank Puffer, May 23 '16 at 21:58
As a slight optimization, you only need to reverse half of the string. — Zymus, May 23 '16 at 22:01
If the code is working, it might be better suited for [Code Review](http://codereview.stackexchange.com/). — Turing85, May 23 '16 at 22:04
The main inefficiency is in editing the new string with `.insert()`. There is a much better way to solve it. Take the original string. Create another string to reverse it. Walk the string (no editing required) starting at the first character, looking for exact character to character matches, allowing exactly one character removal. If you get halfway through the string with only one error you're done. — Daniel Widdis, May 23 '16 at 22:19

score 11 · Accepted Answer · 2016-05-24T10:18:20.807

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 ;)

Thanks for the thorough explanation. I understand the concept, I just need to wrap my head around some of the details. — Rocky, May 23 '16 at 23:38
Please fix your sample solution, it isn't even syntactically valid. — Markus, May 24 '16 at 08:17
@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 — , May 24 '16 at 09:06
@Markus fixed. That was nothing but a few typos and lines I forgot to delete — , May 24 '16 at 09:16
@Paul Thanks for taking the time. I think code examples posted here should be at least syntactically valid. — Markus, May 24 '16 at 10:07
@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. — , May 24 '16 at 10:14

Stephen C · Answer 2 · 2016-05-24T07:26:19.753

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:

Adding or removing a character from a StringBuilder
Creating a new StringBuilder from an existing StringBuilder
Reversing a StringBuilder
Creating a String from a StringBuilder (toString())
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.

score 0 · Answer 3 · answered Jun 05 '20 at 08:07

We can solve this using LCS(Longest Common Sub-sequence). LCS tells us the length of the longest sub-sequence in two strings.

boolean isPalindromAfterRemovingOneChar(String s) {
    int lengthOfLCS = lcs(s, s.reverse(), s.length());
    return (s.length()- lengthOfLCS) == 1;
}

score 0 · Answer 4 · answered Jul 24 '22 at 18:25

function test(s) {
const check = isPalindrome(s)
if (!check) {
    const arr = s.split('')
    const arrCheck = []
    arr.forEach((element, i) => {
        if (element !== arr[arr.length - i - 1]) {
            const news = Array.from(arr)
            console.log(arr, news.splice(i, 1))
            isPalindrome(news.join(''))
        }
    });
    console.log('arrCheck', arrCheck)
}


function isPalindrome(s) {
var reversedString = s.split("").reverse().join("");
if (s === reversedString) {
    console.log('this string is palindrome', s)
    return true
} else {
    console.log('no')
    return false
}

test('aaab')

score -1 · Answer 5 · answered May 23 '16 at 22:29

Only need to compare the first half to the second half. Don't waste time reversing the whole String either.

private boolean isPalindrome(String string) {
    char[] values = string.toCharArray();

    for (int i = 0; i < values.length / 2; i++) {
       if (values[i] != values[values.length - 1 - i])
           return false;
    }

    return true;
}

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

5 Answers5