Longest Common Subsequence Problem Statement

Given two strings, S and T with respective lengths M and N, your task is to determine the length of their longest common subsequence.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, in the string "abc", the subsequences include "", "a", "b", "c", "ab", "bc", "ac", "abc", among others.

Input:

The first line contains the string 'S' of length 'M'.
The second line contains the string 'T' of length 'N'.

Output:

Return the length of the Longest Common Subsequence as an integer.

Example:

Input:

S = "abcde"
T = "ace"

Output:

3

Explanation:

The Longest Common Subsequence is "ace".

Constraints:

0 ≤ M ≤ 10³

0 ≤ N ≤ 10³

Time Limit: 1 second

Question

Longest Common Subsequence Problem Statement

Given two strings, S and T with respective lengths M and N, your task is to determine the length of their longest common subsequence.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, in the string "abc", the subsequences include "", "a", "b", "c", "ab", "bc", "ac", "abc", among others.

Input:

The first line contains the string 'S' of length 'M'.
The second line contains the string 'T' of length 'N'.

Output:

Return the length of the Longest Common Subsequence as an integer.

Example:

Input:

S = "abcde"
T = "ace"

Output:

Explanation:

The Longest Common Subsequence is "ace".

Constraints:

0 ≤ M ≤ 10³
0 ≤ N ≤ 10³
Time Limit: 1 second

Accepted Answer

The task is to find the length of the longest common subsequence between two given strings.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
We can solve this problem using dynamic programming.
Create a 2D array to store the lengths of the longest common subsequences for all possible prefixes of the two strings.
Iterate through the strings and fill the array based on the following conditions: if the characters match, add 1 to the length of the previous longest common subsequence; otherwise, take the maximum of the lengths of the previous subsequences.
The last element of the array will contain the length of the longest common subsequence.

Longest Common Subsequence Problem Statement

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

Popular interview questions of Software Developer Intern