//{ 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] ; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter