Count how many palindromes in a string

Question

I want to find out all possible palindromes that can be possible using substrings from a given string.

Example: input = abbcbbd.
Possible palindromes are a,b,b,c,b,b,d,bb,bcb, bbcbb,bb

Here is the logic I have implemented:

public int palindromeCount(String input) {
    int size = input.length();// all single characters in string are treated as palindromes.
    int count = size;
    for(int i=0; i<size; i++) {
        for(int j=i+2; j<=size; j++) {
            String value = input.substring(i, j);
            String reverse = new StringBuilder(value).reverse().toString();
            if(value.equals(reverse)) {
                count++;
            }
        }
    }
    return count;
}

Here the time complexity is more, how can I improve the performance of this logic?

Answer 1

Here are some things you can think about when optimizing this algorithm:

1. What are palindromes? A palindrome is a symmetrical string, which means it must have a center pivot! The pivot may be one of the following:

   • A letter, as in "aba", or

   • The position between two letters, as in the position between the letters "aa"

That means there are a total of 2n − 1 possible pivots.

Then, you can search outwards from each pivot. Here is an example:

• Sample string: "abcba"
• First, let's take a pivot at "c":
  • abcba → c is a palindrome, then widen your search by 1 on each side.
  • abcba → bcb is a palindrome, then widen your search by 1 on each side.
  • abcba → abcba is a palindrome, so we know there are at least 3 palindromes in the string.
• Continue this with all pivots.

Which this approach, the runtime complexity is O(n²).