kotlin coding test course, longest common subsequence

1. Introduction

The key to algorithm problem solving is to develop the ability to understand and solve various problems. Among them, the Longest Common Subsequence (LCS) problem is a fundamental problem that frequently appears in several algorithm tests. In this article, we will take a closer look at the process of solving the LCS problem using Kotlin.

2. Problem Description

Given two strings, the problem is to find the length of the longest subsequence that appears in both strings without deleting any characters. In other words, it is to find the longest subsequence that can be formed while maintaining the order of characters in both strings.

Example

• String 1: “ABCBDAB”
• String 2: “BDCAB”
• Longest Common Subsequence: “BCAB” (Length: 4)

3. Approach to Problem Solving

A common approach to solve the LCS problem is Dynamic Programming. Dynamic Programming is a methodology for solving complex problems by breaking them down into simpler subproblems. Here, we will compare each character of the two strings and calculate the maximum length.

3.1. Defining the Dynamic Programming Table

First, let the lengths of the two strings be m and n, and define dp[i][j] as the length of the LCS of the first i characters of string 1 and the first j characters of string 2. The size of this table is (m+1) x (n+1). The first row and column of the table are initialized to 0.

3.2. Setting the Recurrence Relation

The table will be filled according to the following rules, comparing characters up to the last character of both strings:

• When characters are the same: dp[i][j] = dp[i-1][j-1] + 1
• When characters are different: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3.3. Extracting the Result

The last cell dp[m][n] of the completed dp table contains the length of the LCS for the two strings.

4. Kotlin Implementation

Now, based on the theoretical explanation, let’s calculate the LCS using Kotlin.

fun longestCommonSubsequence(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    for (i in 1..m) {
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[m][n]
}

fun main() {
    val s1 = "ABCBDAB"
    val s2 = "BDCAB"
    println("Length of Longest Common Subsequence: ${longestCommonSubsequence(s1, s2)}")
}
            

5. Analysis

The above code has a time complexity of O(m * n) and a space complexity of O(m * n). Therefore, as the length of the strings increases, performance may decrease. However, the LCS problem can be improved through various optimization techniques.

5.1. Improving Space Efficiency

Currently, a 2D array is used, but since only the previous row’s values are needed, it can also be solved with a 1D array. This can reduce the space complexity to O(n).

fun longestCommonSubsequenceOptimized(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = IntArray(n + 1)

    for (i in 1..m) {
        val prev = IntArray(n + 1)
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = prev[j - 1] + 1
            } else {
                dp[j] = maxOf(dp[j - 1], prev[j])
            }
            prev[j] = dp[j]
        }
    }
    return dp[n]
}
            

6. Conclusion

The Longest Common Subsequence problem is a very important problem in algorithm study and code testing. It can be efficiently solved using dynamic programming, and we have learned that there are various optimization techniques. I hope this problem provides an opportunity to develop algorithmic thinking and practice Kotlin programming.