Q30 Count Palindromic Subsequences | Practice | GeeksforGeeks
Sun Mar 26 2023 09:21:51 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//{ Driver Code Starts
import java.util.*;
class GFG
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
while(t>0)
{
String str = sc.nextLine();
//System.out.println(str.length());
Solution ob = new Solution();
System.out.println(ob.countPS(str));
t--;
}
}
}
// } Driver Code Ends
/*You are required to complete below method */
class Solution
{
long countPS(String s)
{
//making 2d dp array, S&m - every cell denotes LPS of that string
long mod = 1000000000 + 7;
int n = s.length();
long[][] dp = new long[n][n];
for(int gap = 0 ; gap < n ; gap++){
for(int i = 0 , j = gap; j < n ; i++ , j++){
if(gap == 0)
dp[i][j] = 1; //for 1 character string CPS = 1
//for 2char string , CPS = 3 if c1=c2 else CPS = 2
else if(gap == 1)
dp[i][j] = s.charAt(i)==s.charAt(j) ? 3 : 2;
//i denotes prefix , j denotes suffix
else{
//if c1 == c2 , CPS of prefix + suffix + 1 (for c1+empty subsequence+c2)
if(s.charAt(i) == s.charAt(j))
dp[i][j] = 1 + dp[i][j-1] + dp[i+1][j] ;
//else CPS of suffix + prefix - middlepart
else
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
}
}
}
// for(int i = 0 ; i < n ; i++){
// for(int j = 0 ; j < n ;j++)
// System.out.print(dp[i][j] + " ");
// System.out.println();
// }
return dp[0][n-1] ;
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1
Comments