educative.io

Educative

Count of Palindromic Substrings

Can anyone share recursive Java solution for the same??

4 Likes

Hi,

Thanks for reaching out to us. We are looking into your query and will get back to you soon.

Please let us know if you have any further queries.

Hi Krish,

Here you go.

public class CPS {

  public int countPS(String st) {
    return countPSRecursive(st, 0, st.length()-1);
  }

  private int countPSRecursive(String st, int startIndex, int endIndex) {
    if(startIndex > endIndex)
      return 0;

    // every string with one character is a palindrome
    if(startIndex == endIndex)
      return 1;

    int totalPSCount = 0;
    if(isPalindrome(st, startIndex, endIndex))
      totalPSCount = 1;    
    
    // count all palindromes from "startIndex+1" to "endIndex"
    totalPSCount += countPSRecursive(st, startIndex+1, endIndex);
    // count all palindromes from "startIndex" to "endIndex-1"
    totalPSCount += countPSRecursive(st, startIndex, endIndex-1);
    // because of the above two recursive calls, since we have counted twice all 
    // palindromes from "startIndex+1" to "endIndex-1", let's subtract one count
    totalPSCount -= countPSRecursive(st, startIndex+1, endIndex-1);
    
    return totalPSCount;
  }
  
  private boolean isPalindrome(String st, int x, int y) {
    while(x <= y) {
      if(st.charAt(x++) != st.charAt(y--))
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    CPS cps = new CPS();
    System.out.println(cps.countPS("abdbca"));
    System.out.println(cps.countPS("cddpd"));
    System.out.println(cps.countPS("pqr"));
    System.out.println(cps.countPS("qqq"));
  }
}
8 Likes

Here is a simplified version, aligned withe the DP solution. For the top down, we just have to memoize the isPalindrome().

public class CPS {

  public int countPS(String st) {

    // every single character is a palindrome
    int totalPSCount = st.length();

    // find all palindromes of "length > 1"
    for (int endIndex=0; endIndex < st.length(); endIndex++) {
      for (int startIndex=0; startIndex < endIndex; startIndex++) {
        if(isPalindrome(st, startIndex, endIndex))
          totalPSCount++;
      }
    }
    
    return totalPSCount;
  }
  
  private boolean isPalindrome(String st, int x, int y) {
    while(x <= y) {
      if(st.charAt(x++) != st.charAt(y--))
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    CPS cps = new CPS();
    System.out.println(cps.countPS2("abdbca"));
    System.out.println(cps.countPS2("cddpd"));
    System.out.println(cps.countPS2("pqr"));
    System.out.println(cps.countPS2("qqq"));
  }
}
1 Like

Thank you for quick response, is what I am looking for.

What’s the time complexity and space complexity of both solutions?

If we memoize the isPalindrome results then its bottom up approach. Can you please tell us the top down approach with memoization for this problem.

1 Like

Thanks, but this top down approach is on a different line than top down approach for the Longest Palindromic Subsequence.

1 Like

Is it expected from someone to come up with this recursive approach on their own or first attempt?

Yep, the pure Top-Down approach is different from the Longest Palindromic Substring top-down solution.
This should be added to the article.

1 Like