# HelloKoding

Practical coding guides

# Longest Common Subsequence

## Problem

• Given two strings, `S` of length `m` and `T` of length `n`
• Write an algorithm to find the length of the longest common subsequence (LCS) of both `S` and `T`

## Example

• Input: given two strings “XMJYAUZ” and “MZJAWXU”
• Expected output: 4 (the LCS is “MJAU”)

## Approach: Bottom Up Dynamic Programming

• Optimal substructure: `L(i, j) = L(i-1, j-1) + 1` if `S(i-1) == T(j-1)` with `L(i, j)` is the length of the common subsequence at character `S(i)` and `T(j)`

For the above example, the LCS “MJAU” has the length at the last common character `U` of both `S` and `T`, `L(6, 7)`, equals to the length at the immediate preceding common character `A`, `L(5, 4)`, plus 1

• Bottom up filling the 2D array `L[m+1][n+1]`. The length of the LCS is at `L[m][n]`

## Implementation

DP_LongestCommonSubsequence.java

``````package com.hellokoding.algorithm;

public class DP_LongestCommonSubsequence {
static int lengthOfLongestCommonSubsequence(String S, String T) {
int m = S.length();
int n = T.length();
int[][] lengths = new int[m+1][n+1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if(S.charAt(i-1) == T.charAt(j-1)) {
lengths[i][j] = lengths[i-1][j-1] + 1;
} else {
lengths[i][j] = Math.max(lengths[i-1][j], lengths[i][j-1]);
}
}
}

return lengths[m][n];
}

public static void main(String[] args) {
System.out.println(lengthOfLongestCommonSubsequence("XMJYAUZ", "MZJAWXU"));
}
}
``````

## Complexity

• Time complexity: O(mn)
• Space complexity: O(mn)