educative.io

Count of Palindromic Substrings

Courses
,
#1

Can anyone share recursive Java solution for the same??

3 Likes
#2

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.

#3

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"));
  }
}
7 Likes
Count of substrings using recursion and top down approach
#4

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
#5

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

#6

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

#7

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
#8

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

1 Like
#9

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

#13

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