Longest Common Subsequence (LCS) - Classic Problems | Repovive

CLS10. Longest Common Subsequence (LCS)

1s256 MB

Given two strings $s$ and $t$ , find the length of their longest common subsequence.

A subsequence is a sequence that can be derived by deleting some or no elements without changing the order of remaining elements.

\begin{array}{l} s \\ t \end{array}

$\text{length of LCS}$

Input

abcde
ace

Explanation

For this input, the required output is 3.

Output

Input

abc
abc

Explanation

For this input, the required output is 3.

Output

Input

abc
def

Explanation

For this input, the required output is 0.

Output

Given two strings $s$ and $t$ , find the length of their longest common subsequence.

A subsequence is a sequence that can be derived by deleting some or no elements without changing the order of remaining elements.

\begin{array}{l} s \\ t \end{array}

$\text{length of LCS}$