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