### 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 1Bottom up filling the 2D array

`L[m+1][n+1]`

. The length of the LCS is at`L[m][n]`

#### Implementation

```
```

#### Complexity

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