Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find all substrings that are palindromes

If the input is 'abba' then the possible palindromes are a, b, b, a, bb, abba.
I understand that determining if string is palindrome is easy. It would be like:

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

But what is the efficient way of finding palindrome substrings?

like image 582
Himanshu Yadav Avatar asked Nov 05 '13 23:11

Himanshu Yadav


People also ask

How do you find a substring palindrome?

Approach: The simple approach is to check each substring whether the substring is a palindrome or not. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

How many Substrings are scatter palindromes?

The scatter-palindromes are a,aa,aab,aabb,b,bb,b there are 9 substrings that are scatter-palindromes.


3 Answers

This can be done in O(n), using Manacher's algorithm.

The main idea is a combination of dynamic programming and (as others have said already) computing maximum length of palindrome with center in a given letter.


What we really want to calculate is radius of the longest palindrome, not the length. The radius is simply length/2 or (length - 1)/2 (for odd-length palindromes).

After computing palindrome radius pr at given position i we use already computed radiuses to find palindromes in range [i - pr ; i]. This lets us (because palindromes are, well, palindromes) skip further computation of radiuses for range [i ; i + pr].

While we search in range [i - pr ; i], there are four basic cases for each position i - k (where k is in 1,2,... pr):

  • no palindrome (radius = 0) at i - k
    (this means radius = 0 at i + k, too)
  • inner palindrome, which means it fits in range
    (this means radius at i + k is the same as at i - k)
  • outer palindrome, which means it doesn't fit in range
    (this means radius at i + k is cut down to fit in range, i.e because i + k + radius > i + pr we reduce radius to pr - k)
  • sticky palindrome, which means i + k + radius = i + pr
    (in that case we need to search for potentially bigger radius at i + k)

Full, detailed explanation would be rather long. What about some code samples? :)

I've found C++ implementation of this algorithm by Polish teacher, mgr Jerzy Wałaszek.
I've translated comments to english, added some other comments and simplified it a bit to be easier to catch the main part.
Take a look here.


Note: in case of problems understanding why this is O(n), try to look this way:
after finding radius (let's call it r) at some position, we need to iterate over r elements back, but as a result we can skip computation for r elements forward. Therefore, total number of iterated elements stays the same.

like image 79
Michał Rybak Avatar answered Sep 21 '22 16:09

Michał Rybak


Perhaps you could iterate across potential middle character (odd length palindromes) and middle points between characters (even length palindromes) and extend each until you cannot get any further (next left and right characters don't match).

That would save a lot of computation when there are no many palidromes in the string. In such case the cost would be O(n) for sparse palidrome strings.

For palindrome dense inputs it would be O(n^2) as each position cannot be extended more than the length of the array / 2. Obviously this is even less towards the ends of the array.

  public Set<String> palindromes(final String input) {

     final Set<String> result = new HashSet<>();

     for (int i = 0; i < input.length(); i++) {
         // expanding even length palindromes:
         expandPalindromes(result,input,i,i+1);
         // expanding odd length palindromes:
         expandPalindromes(result,input,i,i);
     } 
     return result;
  }

  public void expandPalindromes(final Set<String> result, final String s, int i, int j) {
      while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            result.add(s.substring(i,j+1));
            i--; j++;
      }
  }
like image 43
Valentin Ruano Avatar answered Sep 25 '22 16:09

Valentin Ruano


So, each distinct letter is already a palindrome - so you already have N + 1 palindromes, where N is the number of distinct letters (plus empty string). You can do that in single run - O(N).

Now, for non-trivial palindromes, you can test each point of your string to be a center of potential palindrome - grow in both directions - something that Valentin Ruano suggested.
This solution will take O(N^2) since each test is O(N) and number of possible "centers" is also O(N) - the center is either a letter or space between two letters, again as in Valentin's solution.

Note, there is also O(N) solution to your problem, based on Manacher's algoritm (article describes "longest palindrome", but algorithm could be used to count all of them)

like image 30
kiruwka Avatar answered Sep 24 '22 16:09

kiruwka