Skip to main content

Longest Palindromic Subsequence in Java Vijay Sinha The Crazy Programmer

In this article, we will look at yet another interesting problem popular in coding interviews. The problem states that Given a String we have to Find the Longest Palindromic Subsequence present in the String. We need to find only the Length of such subsequence. We will discuss various approaches related to our problem and analyze the time and space complexities.

By Subsequence, we mean a sequence of string characters not necessarily contiguous but they have to preserve their relative ordering. For Example, for the String : ABBHJ, AHJ is a subsequence of the string, because characters follow the order and each of them are present in the String. Now, we need to find a Palindromic Subsequence. E.g. For String, CBAFAB, BAAB and BAFAB are subsequences of the string and are palindrome. But Subsequence BAFAB is the longest among them with length 5.

Note: If a sequence of characters is contiguous it is a Substring. A substring is also a Subsequence.

Let us look at different approaches to solve this problem.

Approach 1 (Recursive Approach)

The Key steps to implement in this approach are:

  • We have two pointers: Left Pointer: Contains start index of string, Right Pointer: Contains last index end of string. We first check if the given string is of length 1 i.e. if value of left and right are same we return 1 as a single character string is palindrome.
  • Now, If the first character and the last character of the string matches, we add two to our result and recursively call for left+1 and right-1 index of the string.
  • If the characters at left and right index do not match then we search for a palindromic string between indexes (left+1, right) and (left, right-1) of the string, we consider the length obtained from the maximum of the two for each recursive call and keep on adding them to the result until we reach the base case.
Input : DABCFCBAG
Output : 7           // Here ABCFCBA IS Longest Palindromic Subsequence

Let us look at the code in Java:

class LongestPalindrome 
{ 
    // Returns the length of the Longest palindromic subsequence 
  
    static int longestPalindromeRecursive(String str, int left, int right) 
    { 
        // Boundary Check.
        if (left > right) { 
            return 0; 
        } 
        
        //If there is only 1 character or left = right.
        if(left == right)
        return 1;
  
        // If the characters at left and right index do match.  
        if (str.charAt(left) == str.charAt(right) ) 
        { 
            return 2 + longestPalindromeRecursive(str,left+1,right-1); 
        } 
  
  
        // If the first and last characters do not match  
        return Math.max(longestPalindromeRecursive(str, left, right - 1), longestPalindromeRecursive(str, left + 1, right)); 
    } 
  
    public static void main(String[] args) { 
        String str = "CBAFAB"; 
        int n = str.length(); 
        int result= longestPalindromeRecursive(str, 0, n - 1);
        System.out.print("The Length of the Longest Palindrome is: "+result); 
  
    } 
}

Output:

The Length of the Longest Palindrome is: 5

Time Complexity: We break each problem into 2 more sub problems in every recursive call. The time complexity is exponential in this case leading to O (2) complexity.

Approach 2 (Dynamic Programming)

We apply Dynamic Programming on Overlapping Subproblems. If there are problems which are computed again and again we can apply dynamic programming by storing results of previously occurred subproblems. This is the first property, the other one is Optimal Substructure, the problems whose final solution can be achieved by results of their subproblems. We see, both properties are evident in the recursive solution discussed above. So we apply Dynamic Programming. There are two approaches to discuss :

Top to Bottom Approach

In this approach we basically store the result of recursive solutions of each subproblem in a 2D Array for overlapping subproblems, to avoid repeated computations.

Let us look at the implementation of this approach in Java:

class LongestPalindrome 
{ 
    // Returns the length of the Longest palindromic subsequence 
  
    public static int longestPalindromeTop_To_Bottom(String str, int left, int right, Integer[][] arr) 
    {
    //Boundary check
    if(left > right)
      return 0;
    
    if(left == right) {
      return 1;
    }
    
    if(arr[left][right] == null) 
    {
      if(str.charAt(left) == str.charAt(right)) 
      {
        arr[left][right] = 2 + longestPalindromeTop_To_Bottom(str, left + 1, right - 1, arr);
      } 
      else 
      {
        arr[left][right] = Math.max(longestPalindromeTop_To_Bottom(str, left + 1, right, arr), longestPalindromeTop_To_Bottom(str, left, right - 1, arr));  
      }  
    }

    return arr[left][right];
  }
  
    public static void main(String[] args) 
    { 
        String str = "CABEEBAF"; 
        int n = str.length(); 
        
        Integer arr[][]=new Integer[n][n];
        int result= longestPalindromeTop_To_Bottom(str, 0, n - 1, arr);
        
        System.out.print("The Length of the Longest Palindrome is: "+result); 
  
    } 
}

Output:

The Length of the Longest Palindrome is: 6

Explanation: We use a 2D array to store the results obtained for each recursive call. We use Wrapper Class Integer array not primitive type because primitive type integer array initializes elements to zero. So to avoid confusion with our result which for some cases might give 0 we use it and Integer type array are initialized to null. So we check for the string with index left and right if the solution is not present in our array we recursively compute it (Like Previous Solution) and store it in our array. If the result is already computed we just return the result at index left and right. In such a case, there is no need of computing the same problem.

Time Complexity: The Time Complexity of this solution is O (n2), as we skip computing solutions of overlapping subproblems, we just return the already existing value.  The complexity is not exponential in this case.

Space Complexity: We use a 2D array of size equal to length of the string, n so overall complexity is O(n2).

Bottom Up Approach

In this approach we will first solve the basic bottom solutions or base cases first, then we find the actual solution of subproblems and the whole problem. Here, we check each combination and get the maximum palindromic length. For each subsequence, we check how many palindromic subsequences are possible with it and get its maximum length. We can start from the start or end of the string.

This is an iterative approach, we fill the 2D array from the right diagonal half. Here, we fill the diagonal elements as 1 because a single character is a palindrome of length 1. So, apart from the diagonal elements if the left and right characters do not match then:  Arr [left] [right]=Max( Arr[left+1] [right], Arr[left] [right-1] ).

If characters match then Arr[left][right]= 2+ Arr[left+1][right-1].

So, for the String ABEFBAC, The 2D array or tabulation look like this:

Longest Palindromic Subsequence

Note: We fill the table from the bottom and the max length is present at Arr[0] [n-1].

So let us have a look at the implementation of the above in Java:

class LongestPalindrome 
{ 
    // Returns the length of the Longest palindromic subsequence 
  
    public static int longestPalindromeBottomUp(String str, int n) 
    {
        
    int[][] arr = new int[n][n];
    // Initialize diagonal elements as 1.
    for (int i = 0; i < str.length(); i++) 
    {
      arr[i][i] = 1;
    }
      
    for(int left = n - 2; left >= 0; left--) 
    {
      for(int right = left + 1; right < n; right++) 
      {
        
        if(str.charAt(left) == str.charAt(right)) 
        {
          arr[left][right] = 2 + arr[left + 1][right - 1];
        } 
        else 
        {
          arr[left][right] = Math.max(arr[left + 1][right], arr[left][right - 1]);
        }
      }
    }
    // return the max length.
    return arr[0][n - 1];
  }
    public static void main(String[] args) 
    { 
        String str = "ABEFBAC"; 
        int n = str.length(); 
        
        int result= longestPalindromeBottomUp(str, n);
        
        System.out.print("The Length of the Longest Palindrome is: "+result); 
  
    } 
}

Output:

The Length of the Longest Palindrome is: 5

Time Complexity: The complexity is O (n2) as above it is still effective being an iterative approach.

Space Complexity: It is O (n2), as we use a 2D array for the tabulation shown above.

So that’s it for the article you can try out the problem with different examples to test your understanding and execute the code too in your local compiler.

Feel free to leave suggestions or doubts (if any) in the comments section below.

The post Longest Palindromic Subsequence in Java appeared first on The Crazy Programmer.



from The Crazy Programmer https://ift.tt/3c2ccMN

Comments

Popular posts from this blog

Difference between Web Designer and Web Developer Neeraj Mishra The Crazy Programmer

Have you ever wondered about the distinctions between web developers’ and web designers’ duties and obligations? You’re not alone! Many people have trouble distinguishing between these two. Although they collaborate to publish new websites on the internet, web developers and web designers play very different roles. To put these job possibilities into perspective, consider the construction of a house. To create a vision for the house, including the visual components, the space planning and layout, the materials, and the overall appearance and sense of the space, you need an architect. That said, to translate an idea into a building, you need construction professionals to take those architectural drawings and put them into practice. Image Source In a similar vein, web development and design work together to create websites. Let’s examine the major responsibilities and distinctions between web developers and web designers. Let’s get going, shall we? What Does a Web Designer Do?

A guide to data integration tools

CData Software is a leader in data access and connectivity solutions. It specializes in the development of data drivers and data access technologies for real-time access to online or on-premise applications, databases and web APIs. The company is focused on bringing data connectivity capabilities natively into tools organizations already use. It also features ETL/ELT solutions, enterprise connectors, and data visualization. Matillion ’s data transformation software empowers customers to extract data from a wide number of sources, load it into their chosen cloud data warehouse (CDW) and transform that data from its siloed source state, into analytics-ready insights – prepared for advanced analytics, machine learning, and artificial intelligence use cases. Only Matillion is purpose-built for Snowflake, Amazon Redshift, Google BigQuery, and Microsoft Azure, enabling businesses to achieve new levels of simplicity, speed, scale, and savings. Trusted by companies of all sizes to meet

2022: The year of hybrid work

Remote work was once considered a luxury to many, but in 2020, it became a necessity for a large portion of the workforce, as the scary and unknown COVID-19 virus sickened and even took the lives of so many people around the world.  Some workers were able to thrive in a remote setting, while others felt isolated and struggled to keep up a balance between their work and home lives. Last year saw the availability of life-saving vaccines, so companies were able to start having the conversation about what to do next. Should they keep everyone remote? Should they go back to working in the office full time? Or should they do something in between? Enter hybrid work, which offers a mix of the two. A Fall 2021 study conducted by Google revealed that over 75% of survey respondents expect hybrid work to become a standard practice within their organization within the next three years.  Thus, two years after the world abruptly shifted to widespread adoption of remote work, we are declaring 20