Print all the palindromic substrings of a given string


  • 1
    S

    Question was to find all possible palindromic substrings of a given string.I answered O(n^2) method where I generated all the substrings and checked if they are palindrome.But they expected more optimized answer.


  • 0
    R

    I think not n^2 still, as substr need on, and still n^3
    //
    // Created by richard on 16-2-28.
    //

    #include <string.h>
    #include <bits/stdc++.h>
    using namespace std;
    vector<string> generatePalindrome(string& str) {
        int len = str.size();
        bool dp[len][len] ;
        memset(dp, sizeof dp, 1);
        for(int l = 2 ; l <= len; l ++ ) {
            for(int i = 0; i < len; i ++ ) {
                int j = i + l - 1;
                if(j>=len) {
                    continue;
                }
                dp[i][j] = dp[i+1][j-1] && str[i] == str[j];
            }
        }
        vector<string> ans;
        for(int i = 0; i < len; i ++) {
            for(int j = i; j < len; j ++ ) {
                if(dp[i][j]) {
                    ans.push_back(str.substr(i, j - i + 1));
                }
            }
        }
        return ans;
    }

  • 1
    S

    This is an O(n^2) solution. And does not use extra space that dp would use. Auxillary space is needed for storing results to avoid duplicate values from result.

    The approach is simple. Pick a character and move left and right from it. If these strings are palindromic then continue moving else break. Tricky part is to handle Palindromic strings of Odd and Even lengths.

    Code Link: https://github.com/shivam-maharshi/Algorithms/blob/master/src/string/PrintAllPalindromicSubstrings.java

    /**

    • Find all the Palindromic substrings of a given string.

    • Link:

    • http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-

    • given-string/

    • @author shivam.maharshi
      */
      public class PrintAllPalindromicSubstrings {

      /*

      • The idea is to simply pick every character and move both the sides till
      • the characters are same on the end. If they are not, then you break of
      • the loop because if the substring is not a palindrome than the bigger
      • string will not be a plaindrome too. TimeComplexity: O(n^2). Brute force
      • is O(n^3). Generation of all substring of a string is itself O(n^2),
      • hence this is an optimal solution.
        */
        public static Set<String> printAll(String s) {
        Set<String> res = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
        StringBuilder sb = new StringBuilder();
        int j = i, k = i + 1;
        res.add(s.charAt(i) + "");
        for (int it = 0; it < 2; it++) {
        if (it == 1) {
        j = i - 1;
        k = i + 1;
        sb.setLength(0);
        sb.append(s.charAt(i));
        }
        while (j >= 0 && k < s.length()) {
        if (s.charAt(j) == s.charAt(k)) {
        sb.insert(0, s.charAt(j));
        res.add(sb.append(s.charAt(k)).toString());
        j--;
        k++;
        } else
        break;
        }
        }
        }
        return res;
        }

      public static void main(String[] args) {
      for (String s : printAll("abcbad"))
      System.out.println(s);
      }

    }


  • 0

    this could be solved in O(n) using Manacher's algorithm, however to be honest if you didn't see or know the algorithm before it's hard (IMO) to come up with on your own in 45 minutes!


  • 0
    S

    @k' I don't think O(n) is possible since the questions asks for all substring and not the longest. I think O(n^2) is the best we can do.

    Reference: http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/


  • 1

    @shivam.maharshi Please see below from Wikipedia page

    Manacher (1975) found a linear time algorithm for listing all the palindromes that appear at the start of a given string. However, as observed e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in linear time.


  • 0
    S

    @k' Thanks for sharing!


  • 0

    @shivam.maharshi my pleasure, but honestly I think it's just not fair to ask this question in 45 minutes interview and expect to answer it if you don't know the algorithm, that's my opinion anyways


  • 0
    S

    @k' I agree. When they ask questions on the algorithms that people publish in paper IMO it's mostly to check your knowledge rather than analytical skills. Maybe it's important for them may be not. But I think that @shashank23 used native library substring function which made the algo O(n^3) instead. Hence I think they were expecting O(n^2).


  • 0
    D

    @shivam.maharshi Your solution is O(n^3). You use StringBuilder to avoid calling substring(), but insert() method is O(n).


  • 0

    I got this question yesterday - slight variation was, I had to return length of longest palindrome substring.


  • 0
    A

    @k' Just a simple addition, I think there are possibly \Omega(n^2) palindromes in a string. Therefore Manacher's algorithm can list all the palindromes in an implicit way as if you are required to print out all palindromes with each starting indices and ending indices, the task is already \Omega(n^2). The thing is that Manacher's algorithm can find the longest palindromes centered at any character, therefore it implicitly list all palindromes.


  • 1

    Let's do a simple center-and-expand method. This isn't the most ideal method (Manacher's is involved) but it is a typical method that interviewers are looking for.

    def solve(S):
        ans = set()
        N = len(S)
        for center in xrange(2*N - 1):
            left = center / 2
            right = left + center % 2
            while 0 <= left and right < len(S) and S[left] == S[right]:
                ans.add(S[left: right+1])
                left -= 1
                right += 1
        return ans
    

  • 0

    Here is a method using Manacher's algorithm.

    def manachers(S):
       SS = '#' + '#'.join(S) + '#'
       Z = [0] * len(SS)
       center = right = 0
       for i in xrange(1, len(SS)):
           if i < right:
               Z[i] = min(right - i, Z[2 * center - i])
           while (min(len(SS) - i - 1, i) > Z[i] and
                  SS[i + Z[i] + 1] == SS[i - Z[i] - 1]):
               Z[i] += 1
           if i + Z[i] > right:
               center, right = i, i + Z[i]
       return Z
    
    def solve(S):
       M = manachers(S)[1: -1]
       ans = set()
       for center, expand in enumerate(M):
          for e in xrange(expand + 1):
            ans.add(S[(center - e)/2 : (center + e)/2])
       return ans
    

  • 0
    G
     public static void listPalindrome(string s)
            {
                for (int i = 0; i < s.Length; i++)
                {
                    //assuming minimum length of string is 2
                    for (int j = 2; j < s.Length; j++)
                    {
                        if (i + j < s.Length)
                        {
                            char[] x = s.Substring(i, j + 1).ToCharArray();
                            string o = new string(x);
                            Array.Reverse(x);
                            string n = new string(x);
    
    
                            if (o.Equals(n))
                            {
                                Console.WriteLine(o);
                            }
    
    
                        }
                    }
                }
    
            }

Log in to reply
 

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