Java Coding Test Course, Longest Common Subsequence Finding

In this course, we will discuss the problem of “Longest Common Subsequence (LCS)”, which is frequently encountered in coding tests. The LCS problem involves finding the longest common subsequence that can be formed by preserving the relative order of elements in both sequences when given two sequences.

Problem Description

Given two strings str1 and str2, find the length of the longest common subsequence of these two strings.

Input

  • String str1 : “AGGTAB”
  • String str2 : “GXTXAYB”

Output

Length of the longest common subsequence : 4

Problem Solving Process

To solve this problem, we will use the dynamic programming approach. Dynamic programming is a method for solving problems by breaking them down into smaller subproblems and storing the results to efficiently solve the problem.

Step 1: Initialize the Two-Dimensional Array

Create a two-dimensional array dp based on the lengths of strings str1 and str2. The size of this array is (m+1) x (n+1), where

  • m : length of str1
  • n : length of str2

Each element of the array is initialized to 0.

Step 2: Fill the Two-Dimensional Array

Now we will fill the two-dimensional array dp. We will proceed by comparing each character of the strings.

  1. Use a loop to compare each character.
  2. If the characters are the same, set dp[i][j] = dp[i-1][j-1] + 1.
  3. If the characters are different, set dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).

Ultimately, the value of dp[m][n] will be the length of the longest common subsequence.

Step 3: Implement the Code

Now let’s implement this process in Java code.


public class LongestCommonSubsequence {
    public static int lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.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];
    }

    public static void main(String[] args) {
        String str1 = "AGGTAB";
        String str2 = "GXTXAYB";
        System.out.println("Length of the longest common subsequence: " + lcs(str1, str2));
    }
}

Code Analysis

The code above operates in the following manner.

  • It takes two strings as input and creates a dp array based on their lengths.
  • Using a nested loop, it compares the strings and updates values using the dynamic programming method.
  • The output provides the length of the longest common subsequence.

Execution Result

Input: str1 = "AGGTAB", str2 = "GXTXAYB"

Output: Length of the longest common subsequence: 4

Conclusion

In this lecture, we learned how to find the longest common subsequence. We demonstrated how effective it can be to use dynamic programming techniques to solve algorithmic problems. This problem can be applied in various fields and is fundamental knowledge to have when solving algorithm problems.

Furthermore, you can experiment with other string combinations based on the code shared in this lecture, deepening your understanding of the theory. I hope this will greatly assist you in developing your algorithm problem-solving skills.