Q30 Count Palindromic Subsequences | Practice | GeeksforGeeks

PHOTO EMBED

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