2-D Dynamic Programming Two strings

558. Longest Common Subsequence

You are given two strings, text1 and text2. Return the length of the longest string that is a subsequence of both.

A subsequence of a string is what is left after deleting some of its letters, or none, without changing the order of the rest. "ace" is a subsequence of "abcde", but "eca" is not. The letters of a subsequence do not have to sit next to each other.

If the two strings have no letter in common, the answer is 0.

Example 1

Input: text1 = "stone", text2 = "longest"

Output: 3

Explanation: "one" is a subsequence of both: in "longest" its letters sit at indexes 1, 2 and 4. "st" is common too, but shorter, and no common subsequence has 4 letters.

Example 2

Input: text1 = "abc", text2 = "xyz"

Output: 0

Explanation: The strings share no letter, so the only common subsequence is the empty one.

Example 3

Input: text1 = "programming", text2 = "gaming"

Output: 6

Explanation: Every letter of "gaming" appears in "programming" in the same order, so all of text2 is the answer.

Check your understanding

Work out the answer for this input before you write any code.

text1 = "abcd", text2 = "badc"

Constraints

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 hold only lowercase English letters.

Clarifying questions

What you would ask an interviewer before writing any code.