CodeWithYash

 For Both Questions Code Is Same: MINIMUM DELETIONS: class Solution{     static int minimumNumberOfDeletions(String s1) {         StringBuilder sb=new StringBuilder();         sb.append(s1);         String s2=sb.reverse().toString();         int n=s2.length();                  int t[][]=new int[n+1][n+1];                  for(int i=0;i<n+1;i++){             for(int j=0;j<n+1;j++){                 if(i==0 || j==0){                     t[i][j]=0;                 }             }         }                  for(int i=1;i<n+1;i++){      ...

 class Solution {     public int longestPalinSubseq(String s1)     {         StringBuilder sb=new StringBuilder();         sb.append(s1);         String s2=sb.reverse().toString();         int n=s1.length();         return cal(s1,s2,n);     }          public int cal(String a, String b, int n){         int t[][]=new int[n+1][n+1];          for(int i=0;i<n+1;i++){ for(int j=0;j<n+1;j++){ if(i==0 || j==0){ t[i][j]=0; } } } for(int i=01;i<n+1;i++){ for(int j=01;j<n+1;j++){ if(a.charAt(i-1)==b.charAt(j-1)){ t[i][j]=1+t[i-1][j-1]; } else{ t[i][j]=Integer.max(t[i-1][j],t[i][j-1]); } } } return t[n][n];     }                     ...

 import java.util.Scanner; class Solve{ public int cal(String a, String b, int n){ int t[][]=new int[n+1][n+1]; for(int i=0;i<n+1;i++){ for(int j=0;j<n+1;j++){ if(i==0 || j==0){ t[i][j]=0; } } } for(int i=01;i<n+1;i++){ for(int j=01;j<n+1;j++){ if(a.charAt(i-1)==b.charAt(j-1)){ t[i][j]=1+t[i-1][j-1]; } else{ t[i][j]=Integer.max(t[i-1][j],t[i][j-1]); } } } return t[n][n]; } } class LongestPaindromicSubsequence{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); String s=sc.next(); StringBuilder sb=new StringBuilder(); sb.append(s); String b=(sb.reverse().toString()); int n=s.length(); Solve obj=new Solve(); int c=obj.cal(s,b,n); System.out.println(c); } }

 class Solution { public int minOperations(String s1, String s2)  {      int n=s1.length();     int m=s2.length();     int p=cal(s1,s2,n,m);     //System.out.println(p);     return p; }  public int cal(String x, String y, int n, int m){     int t[][]=new int[n+1][m+1];     for(int i=0;i<n+1;i++){         for(int j=0;j<m+1;j++){             if(i==0 ||j==0){                 t[i][j]=0;             }         }     }          for(int i=1;i<n+1;i++){         for(int j=1;j<m+1;j++){             if(x.charAt(i-1)==y.charAt(j-1)){                 t[i][j]=t[i-1][j-1]+1;     ...

 class Solution {     //Function to find the length of the shortest common supersequence of two strings.     public static int shortestCommonSupersequence(String x,String y,int n,int m)     {          int t[][]=new int[n+1][m+1];                  for(int i=0;i<n+1;i++){             for(int j=0;j<m+1;j++){                 if(i==0 || j==0){                     t[i][j]=0;                 }             }         }                  for(int i=1;i<n+1;i++){             for(int j=1;j<m+1;j++){                 if(x.charAt(i-1)==y.charAt(j-1)){     ...

 import java.util.Scanner; class LongestCommonSequencePrint{ public static String cal(String x, String y, int n ,int m){ int t[][]=new int[n+1][m+1]; for(int i=0;i<n+1;i++){ for(int j=0;j<m+1;j++){ if(n==0 || m==0){ t[i][j]=0; } } } for(int i=01;i<n+1;i++){ for(int j=01;j<m+1;j++){ if(x.charAt(i-1)==y.charAt(j-1)){ //t[n][m]=1+cal(x,y,i-1,j-1); //t[i][j]=1+cal(x,y,i-1,j-1); t[i][j]=t[i-1][j-1]+1; } else{ //t[n][m]=Integer.max((cal(x,y,i-1,j)),cal(x,y,i,j-1)); //t[i][j]=Integer.max((cal(x,y,i-1,j)),cal(x,y,i,j-1)); t[i][j]=Integer.max(t[i][j-1],t[i-1][j]); } } } String s=print(x,y,n,m,t); return s; } public static String print(String x, String y, int n, int m, int[][]t){ StringBuilder sb=new StringBuilder(); int i=n; int j=m; while(i>0 && j>0){ if(x.charAt(i-1)==y.charAt(j-1)){ sb.append(x....

 LeetCode: class Solution {     public int longestCommonSubsequence(String a, String b) {       int n=a.length();         int m=b.length();         int t[][]=new int[n+1][m+1];         for(int i=0;i<n+1;i++){             for(int j=0;j<m+1;j++){                 if(i==0 || j==0){                     t[i][j]=0;                 }             }         }         for(int i=1;i<n+1;i++){             for(int j=1;j<m+1;j++){                 if(a.charAt(i-1)==b.charAt(j-1)){                     t[i][j]=t[i-1][j-1]+1;         ...

 import java.util.Scanner; class KnapsackSolve{ public int knapsack(int[] arr, int n, int sum){ int t[][]=new int[n+1][sum+1]; for(int i=0;i<n+1;i++){ for(int j=0;j<sum+1;j++){ t[i][j]=-1; } } if(n==0 && sum==0){ return 1; } if(n==0 && sum!=0){ return 0; } if(sum==0){ return 1; } if(t[n][sum]!=-1){ return t[n][sum];  } else{ if(arr[n-1]>sum){ t[n][sum]=knapsack(arr,n-1,sum); } else{ t[n][sum]=Integer.max(knapsack(arr,n-1,sum),knapsack(arr,n-1,sum-arr[n-1])); } return t[n][sum]; } } } class EqualSumPartitionMemoize{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } int sum=0; for(int i=0;i<n;i++){ sum=sum+arr[i]; } if(sum%2!=0){ System.out.println("false"); System.out.pr...

 import java.util.Scanner; class KnapsackSolve{ public boolean knapsack(int[] arr, int n, int sum){ if(n==0 && sum==0){ return true; } if(n==0 && sum!=0){ return false; } if(sum==0){ return true; } else{ if(arr[n-1]>sum){ return knapsack(arr,n-1,sum); } else{ return (knapsack(arr,n-1,sum) || knapsack(arr,n-1,sum-arr[n-1])); } } } } class EqualSumPartitionRecursive{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } int sum=0; for(int i=0;i<n;i++){ sum=sum+arr[i]; } if(sum%2!=0){ System.out.println("false"); System.out.println("Not possible"); } else{ KnapsackSolve obj1=new KnapsackSolve(); boolean c=obj1.knapsack(arr,n,sum/2); System.out.println(c); } } }

  public   class  Solution {      public   int  solve( int [] arr,  int  sum) {                   //Base Condition          int  n=arr.length;          boolean  t[][]= new   boolean [n+ 1 ][sum+ 1 ];              int  a= 0 ;              for ( int  i= 0 ;i<n+ 1 ;i++){                  for ( int  j= 0 ;j<sum+ 1 ;j++){                      if (i== 0 ){             ...

 import java.util.Scanner; class KnapsackSolve{ public boolean knapsack(int[] arr, int n, int sum){ //Base Condition if(n==0){ return false; } else if(sum==0 && n!=0){ return true; } else if(sum==0 && n==0){ return true; } boolean t[][]=new boolean[n+1][sum+1]; for(int i=1;i<n+1;i++){ for(int j=1;j<sum+1;j++){ t[i][j]=false; } } if(t[n][sum]!=false){ return t[n][sum]; } else{ if(arr[n-1]>sum){ t[n][sum]=knapsack(arr,n-1,sum); } else{ t[n][sum]=knapsack(arr,n-1,sum) || knapsack(arr,n-1,sum-arr[n-1]); } return t[n][sum]; } } } class SubsetSumMemoize{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } int sum=sc.nextInt(); KnapsackSolve obj1=new KnapsackSolve(); b...

import java.util.Scanner; class KnapsackSolve{ public boolean knapsack(int[] arr, int n, int W){ //Base Condition if(n==0 && w!=0){ return false; } else if(W==0){ return true; } else{ if(arr[n-1]>W){ return knapsack(arr,n-1,W); } else{ return knapsack(arr,n-1,W) || knapsack(arr,n-1,W-arr[n-1]) ; } } } } class SubsetSumRecursive{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } int W=sc.nextInt(); KnapsackSolve obj1=new KnapsackSolve(); boolean c=obj1.knapsack(arr,n,W); System.out.println(c); } }

BY RECURSION:  Geeks For Geeks******************************************************************* class Solve{     public int knapsack(int w, int[] arr, int[] val, int n){         if(n==0 || w==0){             return 0;         }         else{             if(arr[n-1]>w){                 return knapsack(w,arr,val,n-1);             }             else{                 return Integer.max(knapsack(w,arr,val,n-1),val[n-1]+knapsack(w-arr[n-1],arr,val,n-1));             }         }     } } class Solution  {      //Function to return max value that can be put in the knapsack of capacity W.         static int knapSack(int w, ...

 import java.util.Scanner; class KnapsackSolve{ public int knapsack(int[] arr, int n, int W , int[] val){ if(n==0 || W==0){ return 0; } else{ if(arr[n-1]>W){ return knapsack(arr,n-1,W,val); } else{ return Integer.max((val[n-1]+knapsack(arr,n-1,W-arr[n-1],val)),(knapsack(arr,n-1,W,val))); } } } } class O1KnapsackRecursion{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; int val[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } for(int i=0;i<n;i++){ val[i]=sc.nextInt(); } int W=sc.nextInt(); KnapsackSolve obj1=new KnapsackSolve(); int c=obj1.knapsack(arr,n,W,val); System.out.println(c); } } Time:O(N*W) Space:O(N*W)

 class Solution {     public long count(int arr[], int m, int n)      {         long t[][]=new long[m+1][n+1];        for(int i=0;i<m+1;i++){            for(int j=0;j<n+1;j++){                if(i==0){                    t[i][j]=0;                }                if(j==0){                    t[i][j]=1;                }            }                    }        for(int i=1;i<m+1;i++){            for(int j=1;j<n+1;j++){                if(arr[i-1]>j){...

 class Solution {     public int findTargetSumWays(int[] nums, int target) {         int sum=0;         for(int i=0;i<nums.length;i++){             sum=sum+nums[i];         }         if((sum+target)%2!=0 || target>sum || target<-sum){             return 0;         }         else{             int val=(sum+target)/2;             int t[][]=new int[nums.length+1][val+1];             int count0=0;             for(int i=0;i<nums.length;i++){                 if(nums[i]==0){                     count0++;                 }     ...

 class Solution { public int minDifference(int arr[], int n)  {   int sum=0;     ArrayList<Integer>aa=new ArrayList<Integer>();     for(int i=0;i<n;i++){         sum=sum+arr[i];     }         boolean t[][]=new boolean[n+1][sum+1];     for(int i=0;i<n+1;i++){         for(int j=0;j<sum+1;j++){             if(i==0){                 t[i][j]=false;             }             if(j==0){                 t[i][j]=true;             }         }     }          for(int i=1;i<n+1;i++){         for(int j=1;j<sum+1;j++){       ...

 class Solution{ public int perfectSum(int arr[],int n, int sum)  {      int t[][]=new int[n+1][sum+1];     for(int i=0;i<n+1;i++){         for(int j=0;j<sum+1;j++){             if(i==0){                 t[i][j]=0;             }             if(j==0){                 t[i][j]=1;             }         }     }     int count=0;     for(int i=1;i<n+1;i++){         for(int j=1;j<sum+1;j++){             if(arr[i-1]>j){                 t[i][j]=t[i-1][j] % 1000000007;             }             el...

 class Solution{     static int equalPartition(int n, int arr[])     {         int sum=0;         for(int i=0;i<n;i++){             sum=sum+arr[i];         }         if(sum%2!=0){             return 0;         }         else{             int t[][]=new int[n+1][sum+1];             sum=sum/2;             for(int i=0;i<n+1;i++){                 for(int j=0;j<sum+1;j++){                     if(i==0){                         t[i][j]=0;                     }           ...

 class Solution{     static boolean isSubsetSum(int n, int arr[], int sum){         boolean [][] t=new boolean[n+1][sum+1];         for(int i=0;i<n+1;i++){             for(int j=0;j<sum+1;j++){                 if(i==0){                     t[i][j]=false;                 }                 if(j==0){                     t[i][j]=true;                 }             }         }                  for(int i=1;i<n+1;i++){             for(int j=1;j<sum+1;j++){                 if(arr[i-...