/*
This program computes BOTH:
1. The length of the Longest Common Subsequence (LCS)
2. The actual LCS subsequence
It uses an efficient dynamic‑programming algorithm:
Time: O(n * m)
Space: O(n * m)
dp[i][j] stores the LCS length between:
s1[0..i-1] and s2[0..j-1]
Recurrence:
If characters match:
dp[i][j] = dp[i-1][j-1] + 1
Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
After filling the DP table, we reconstruct the LCS by
walking backwards from dp[n][m].
*/
fun lcs(s1: String, s2: String): Pair<Int, String> {
val n: Int = s1.length
val m: Int = s2.length
// Create DP table initialized with zeros
val dp: Array<IntArray> = Array(n + 1) { IntArray(m + 1) }
// Fill DP table
for (i in 1..n) {
for (j in 1..m) {
dp[i][j] = if (s1[i - 1] == s2[j - 1]) {
dp[i - 1][j - 1] + 1
} else {
maxOf(dp[i - 1][j], dp[i][j - 1])
}
}
}
// Reconstruct the LCS sequence
val length: Int = dp[n][m]
val lcsChars: CharArray = CharArray(length)
var i: Int = n
var j: Int = m
var index: Int = length - 1
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) {
// Character is part of LCS
lcsChars[index] = s1[i - 1]
index--
i--
j--
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i-- // Move up
} else {
j-- // Move left
}
}
return Pair(length, String(lcsChars))
}
fun main() {
val s1: String = "AGGTAB"
val s2: String = "GXTXAYB"
val (length, sequence) = lcs(s1, s2)
println("String 1: $s1")
println("String 2: $s2")
println("Length of LCS: $length")
println("LCS sequence: $sequence")
}
/*
run:
String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB
*/
