# 1. Introduction

The Longest Common Subsequence (LCS) problem is a classic computer science problem that deals with finding the longest sequence of characters that appear in the same order in both strings, not necessarily contiguous. For example, for strings “ABCBDAB” and “BDCAB”, the LCS is “BCAB”.

# 2. Program Steps

1. Initialize a two-dimensional array *dp* of size *(m+1) x (n+1)* where *m* and *n* are the lengths of the two input strings.

2. Fill the first row and first column with zeros.

3. Traverse through the strings and populate the *dp* array based on comparisons between characters of the two strings.

4. The value *dp[i][j]* will represent the length of LCS of the first *i* characters of string1 and first *j* characters of string2.

5. Return *dp[m][n]* as the length of the LCS for the complete strings.

# 3. Code Program

```
public class LongestCommonSubsequence {
public static void main(String[] args) {
String s1 = "ABCBDAB";
String s2 = "BDCAB";
int result = lcs(s1, s2);
System.out.println("The length of the LCS is: " + result);
}
public static int lcs(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// `dp` array where `dp[i][j]` will contain the length of LCS of s1[0..i-1] & s2[0..j-1]
int[][] dp = new int[m+1][n+1];
// Filling the dp array
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; 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]);
}
}
}
return dp[m][n];
}
}
x
```

### Output:

The length of the LCS is: 4

# 4. Step By Step Explanation

1. We utilize a dynamic programming approach to solve the *LCS* problem. The main idea is to use a *dp* table where each cell *dp[i][j]* represents the LCS length for the first *i* characters of string1 and the first *j* characters of string2.

2. The *dp* table is filled row-wise. When characters from the two strings match, we increment the value from the top-left diagonal cell. If they don't match, we take the maximum value from either directly above or directly to the left.

3. By the end of this process, the value in the bottom-right corner of the *dp* table (*dp[m][n]*) represents the length of the LCS for the complete strings.