Longest Palindromic Subsequence Program (Leetcode)

Longest Palindromic Subsequence Program (Leetcode):

Ex: "bacbbcbbdabadbb"

In the given string the palindrome strings are:

"bbcbb"  &  "bbdabadbb"

Since the "bbdabadbb" is the longest

therefore,the ans is "bbdabadbb".

Program:

import java.io.*;
import java.util.*;
class Longest_Palindromic_Subsequence
{
      public static void main(String args[])
      {
            String s = "bacbbcbbdabadbb";
            String s1[] = s.split("");
            StringBuilder input,temp;
            input = new StringBuilder();
            input.append(s);
            input = input.reverse();
            if(s.equals(input.toString()))
            {
                  System.out.println(s);
            }
            else
            {
                  ArrayList<String> l = new ArrayList<String>();
                  for(int i=0;i<=s.length()-1;i++)
                  {
                        String current = "";
                        for(int j=i;j<=s.length()-1;j++)
                        {
                              current = current + s1[j];
                              temp = new StringBuilder();
                              temp.append(current);
                              temp = temp.reverse();
                              if(current.equals(temp.toString()) &&

                                                         (!l.contains(current)))

                              {

                                          l.add(current);

                              }
                              else if(!l.contains(s1[i]))
                              {

                                          l.add(s1[j]);
                              }
                        }
                  }

                  String max = Collections.max(l, 

                                       Comparator.comparing(String::length));     

                  System.out.println(max);
            }
      }
}

Explanation:

In the string "bacbbcbbdabadbb"

The outer loop(i) first takes 'b' and from inner loop(j) it make strings 'ba, bac, bacb' and so on.

If the conditions follows then it is added in ArrayList.

Then the step is repeated and i points to the index of 'a' then it make string and check for palindrome.

When i points to 'b' 3rd index it make string 'bb , bbc , bbcb , bbcbb'.Here,the 'bb' and 'bbcbb' are palindrome and it gets added to ArrayList.Now the process repeats for remaining string and it prints the Palindrome String with maximum length.