python3

javascript

java

Longest Common Subsequence

Given two sequences, find the length of the longest subsequence present in both of them. Both the strings are of uppercase.

### Input Format

Input consists of three lines,

First-line consists of two space-separated Integers, Length of First String and Second String.
The second line should consist of **First String**
The third line should consist of **Second String**

### Output Format

The output should consist of a single line, The Length of the Longest Subsequence present in both of them.

### Example 1:

```txt
Input:
    6 6
    ABCDGH
    AEDFHR
Output:
    9
Explanation:
    LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3
```

### Example 2:

```txt
Input:
    3 2
    ABC
    AC
Output:
    2
Explanation:
    LCS of "ABC" and "AC" is "AC" of length 2.
```


#### Constraints:

- 1<=size(str1),size(str2)<=103
- Expected Time Complexity : O(|str1|*|str2|)
- Expected Auxiliary Space: O(|str1|*|str2|)

def solve(input, st1, st2):
    # CODE HERE

function solve(input, st1, st2){
// CODE HERE
}

int solve(vector<int> input, string st1, string st2){
//CODE HERE 
}

static int solve(int[] input, String st1, String st2){
//CODE HERE 
}