Java Stream API : Find Longest Common Subsequence

Finding Longest Common Subsequence between two strings using the Java Stream API

Introduction

In this blog post, we will explore how to find the longest common subsequence (LCS) between two strings using the Java Stream API. LCS is the longest sequence of characters that appear in the same order in both input strings. We will use dynamic programming to solve this problem efficiently.

Java Stream API : Find Longest Common Subsequence

Understanding the Problem:

Given two strings, we need to find the length of the longest common subsequence and the actual subsequence itself. For example, for the strings "ABCBDAB" and "BDCAB", the longest common subsequence is "BCAB" with a length of 4.

Approach:

We will use a dynamic programming approach to solve this problem. We will create a 2D array dp[][] where dp[i][j] will store the length of the longest common subsequence between the first i characters of the first string and the first j characters of the second string.

We will then iterate through the characters of both strings. If the characters are equal, we will increment the length of the longest common subsequence by 1. Otherwise, we will take the maximum of the longest common subsequence length up to the previous characters.

Finally, we will backtrack through the dp[][] array to construct the longest common subsequence.

Java Code using Stream API:

import java.util.stream.IntStream;

public class LongestCommonSubsequence {

    public static String findLCS(String s1, String s2) {

        int m = s1.length();

        int n = s2.length();

        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(1, m).forEach(i ->

                IntStream.rangeClosed(1, n).forEach(j -> {

                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                        dp[i][j] = dp[i - 1][j - 1] + 1;

                    } else {

                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

                    }

                }));

        StringBuilder lcs = new StringBuilder();

        int i = m, j = n;

        while (i > 0 && j > 0) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                lcs.insert(0, s1.charAt(i - 1));

                i--;

                j--;

            } else if (dp[i - 1][j] > dp[i][j - 1]) {

                i--;

            } else {

                j--;

            }

        }

        return lcs.toString();

    }

    public static void main(String[] args) {

        String s1 = "ABCBDAB";

        String s2 = "BDCAB";

        System.out.println("Longest Common Subsequence: " + findLCS(s1, s2));

    }

}

Explanation:

- We first create a 2D array dp[][] to store the lengths of the longest common subsequences.

- We then use nested IntStream to iterate through each character of the two strings and calculate the length of the longest common subsequence.

- Finally, we backtrack through the dp[][] array to construct the longest common subsequence.

Conclusion:

In this blog post, we learned how to find the longest common subsequence between two strings using the Java Stream API. The dynamic programming approach allowed us to efficiently solve this problem. The use of streams added a concise and readable way to iterate through the characters of the strings.