Count Palindromes


  • 0
    A

    Count the number of possible palindrome substrings in a string. A palindrome is a word that reads the same way spelled backwards.
    Example:
    input: lasagna.
    Possible palindromes are asa, l,a,s,a,g,n,a.
    output: count is 8.

    input:hellolle
    ellolle,lloll,lol,ll,ll,h,e,l,l,o,l,l,e.
    output:13.


  • 0
    This post is deleted!

  • 0
    A

    I currently have n^2 solution. Anyone has better ideas?

    public class FindNumSubstringPalindromes {
       public static boolean isPalindrome(String s, int start, int end){
    	   if(start==end)
    		   return true;
    	   for(int i = 0; i <=(end-start)/2; i++) {
    		   if(s.charAt(i+start) != s.charAt(end-i))
    			   return false;
    	   }
    		   
    	   
    	   return true;
    	   
    	   
       }
       
       public static int countNumPalindromes(String s) {
    	   int count=0;
    	   for(int i=0; i<s.length(); i++) {
    		   for(int j=s.length()-1; j>=i;j--) {
    			   if(s.charAt(i) == s.charAt(j)) {
    				   if(isPalindrome(s, i, j))
    					   count++;
    			   }
    		   }
    	   }
    	   return count;
       }
       
    }
    

  • 1

    @amulya I believe your algorithm is O(n^3). First the two for loops is evaluating a total of O(n^2) possibilities of starting and ending indices (i,j). Then isPalindrome takes O(n) to run, so total complexity is O(n^3).

    Your algorithm can be optimized to O(n^2) by avoiding re-calculation of isPalindrome.


  • 0

    Seems like a slight variation of Longest Palindromic Substring.


  • 2

    Ocourse O(n^2) is the trivial and should be mentioned I think.
    One suggestion for improvement could be to use Manacher algorithm with O(n) complexity.
    With Manacher algorithm will discover the longest palindrom centered at each character.
    example :
    abcbc
    We know that at "c" longest palindrom has 5 char length. this mean that there are (5+1)/2 palindroms centered at "c"
    We have c, bcb, abcbc palindroms
    We calculate numebr of palindroms centered at each character and sum them to get palindrom count.

    Example :

    | H | E | L | L | O | L | L | E |
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    index | palindrom count
    0 | 0
    h | 1
    2 | 0
    3 | 1
    4 | 0
    5 | 1
    6 | 1 (don't take into acocunt second palindorm with "|")
    7 | 1
    8 | 0
    9 | 4 (longest palindrom at "o" is 7, therefore palindrom count is ( 7+1)/2 = 4
    10 | 0
    11 | 1
    12 | 1
    13 | 1
    14 | 0
    15 | 1
    16 | 0
    1+1+1+1+1+4+1+1+1+1 = 13


  • 1

    @elmirap No, I don't think O(n^2) is trivial. There's several ways you can do it in O(n^2), the Dynamic programming approach or expanding from the center.

    As for Manacher's algorithm in O(n), I don't think anyone is expected to come up with that in a 45 minutes interivew :)


    PS: I have written an article about Manacher's algorithm if anyone is interested in learning about it.


  • 0

    yes, depends on the training .... Manacher is very beautiful but DP solution is more easier to implement
    P.P very good article, code is working and could be borrowed probably :-)


  • 0

    @elmirap Yeah, people who participated in competitive programming may know Manacher's algorithm like the back of their hands, but the majority of people have never heard of it. When and how did you learn about Manacher's algorithm?


  • 0

    @1337c0d3r Yes, right, I learnt Manacher some years ago when I was loooking for a solution for the longest palindrom. As you mentioned there were multiple solutions, but Manacher was the most effective. Actually I understood the algorithm when I wrote it down on a paper. Articles are good but sometimes you can loose yourself in it, but yours is good written and I can also recommend it


  • 0

    @elmirap The best way to learn is to get some hints from the article on how to start, then you work it out by yourself. If you get stuck again refer back to the article. The more you work something out yourself, the more you will learn.


    PS: I was also researching about the O(n) way to solve Longest Palindromic Substring, but during that time (2011) there was not a lot of articles explaining about it. So I wrote my own version to help people in understanding this beautiful algorithm.


  • 0

    @1337c0d3r This is the way to reproduce it for 45 minutes (actually max 15)., to understand the concept behind it


  • 0

    @elmirap :beers:


  • 0
    G

    Just FYI, this was actually a coding challenge in HackerRank and the O(n^3) solution would pass the test cases.


  • 0

    @guilhermesena1 Really? Then their test cases must be weak. O(n^3) seems like a brute force solution. I can't actually think of an algorithm that's worse than O(n^3).


  • 0
    Y

    @1337c0d3r said in Count Palindromes:

    Seems like a slight variation of Longest Palindromic Substring.

    I agree that this question is very similar to longest palindromic substring, which can be solved using dynamic programming with n^2 time complexity.


  • 0

    @guilhermesena1, I will try it then. Actually this is not the first case when people complain in HackerRank against tests which passed at least to 80% with brute force , but with other more sophisticated techinques couldn't pass 50% because of TLE. All depends on test cases actually, especially when there are different operations, amortized time could be better for brute force.
    If we want O(n^2) , I think that method with expanding at the character as a center as @1337c0d3r suggested in https://leetcode.com/articles/longest-palindromic-substring/ is more intuitive than DP, but this depends on personal choices and memory.


  • 5
    R

    Here's the O(n^2) solution. This solution is similar longest Palindromic Substring.
    To further reduce the time complexity, we will have to use variation Manacher's algorithm as suggested.

    public static int countPalindromes(String a) {
    		int globalCount = a.length();
    		for (int mid = 1; mid < a.length() - 1; mid++) {
    			int count = 0;
    
    			int low = mid - 1;
    			int high = mid + 1;
    			while (low >= 0 && high < a.length() && a.charAt(low--) == a.charAt(high++))
    				count++;
    
    			globalCount += count;
    			count = 0;
    
    			low = mid - 1;
    			high = mid;
    			while (low >= 0 && high < a.length() && a.charAt(low--) == a.charAt(high++))
    				count++;
    
    			globalCount += count;
    		}
    
    		return globalCount;
    	}
    

  • 0
    N

    @root Should the outer for loop iterating from 1 to a.length() instead of length()-1?


  • 0
    P

    I think the time complexity is 0(n^2) in worst case.

    
    class Solution {
    
    private:
    
        void count(string &s, int len, int i, int j, int &counter) {
            while(i >= 0 && j < len && s[i] == s[j]) {
                    i--;
                    j++;
                    counter++;
            }
        }
    
    public:
        string longestPalindrome(string s) {
            
            int n = s.length();
            
            int counter = 0;
            
            if (!n)
                return 0;
                
            if (n == 1)
                return 1;
    
            for (int i = 0;i<n;++i) {
            
                if (i == 0) {
                    counter++;
                    continue;
                }
                count(s,n,i-1,i, counter);
                count(s,n,i-1,i-1, counter);
            }
            return counter;
    
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.