DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

Count Palindrome Sub-Strings of a String GeeksForGeeks

Given a string, the task is to count all palindromic sub-strings present in it. Length of palindrome sub-string must be greater than or equal to 2.

Example

N = 5 str = "abaab" Output 3 Explanation: All palindrome substring are : "aba" , "aa" , "baab" 
Enter fullscreen mode Exit fullscreen mode

Solution

 class Solution { public int CountPS(String S, int N) { int count =0; //we will use 2d matrix for it  // as in the below for loops two things are changing that we have  //keep in track starting index and ending index of the string  int dp[][] = new int[N][N]; for(int row[]: dp) Arrays.fill(row,-1); for(int i =0;i<N;i++){ for(int j =i+1;j<N;j++){ if(isPalindrome(S,i,j,dp)==1) count++; } } return count; } public int isPalindrome(String s, int i ,int j,int dp[][]){ if(i>j) return 1; if(dp[i][j]!=-1) return dp[i][j]; if(s.charAt(i)!=s.charAt(j)) return 0; return dp[i][j] = isPalindrome(s,i+1,j-1,dp); } } 
Enter fullscreen mode Exit fullscreen mode

Top comments (0)