Longest Common Subsequence

MediumDynamic Programming2D DP

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given two strings text1 and text2, return the length of their **longest common subsequence**. If there is no common subsequence, return 0. A **subsequence** of a string is a new string formed from the original by deleting zero or more characters without changing the relative order of the characters that remain. For example, "ace" is a subsequence of "abcde", but "aec" is not. A **common subsequence** of two strings is a subsequence that appears in both of them. The characters do not need to be contiguous in either string, but they must appear in the same relative order. Your job is to determine the length of the longest such shared subsequence.

Examples

Input: text1 = "abcde", text2 = "ace"

Output: 3

The longest common subsequence is "ace", which has length 3.

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

Output: 3

The two strings are identical, so the longest common subsequence is "abc" with length 3.

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

Output: 0

There is no character shared between the two strings, so the longest common subsequence is empty.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist only of lowercase English characters.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.