Print all the palindromic substrings of a given string


  • 0
    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.


Log in to reply