Longest Common Subsequence

Medium · 2-D Dynamic Programming

You are given two strings. Find the length of the longest sequence of characters that appears in both strings in the same relative order, though not necessarily touching each other in either original string. Return that length as an integer. If the strings share no such sequence, return 0.

Examples

Input:  text1 = "abcde", text2 = "ace"
Output: 3
Why:    Picking the letters a, c, e from both strings in order gives the longest sequence they share, which has length 3.

Input:  text1 = "abc", text2 = "abc"
Output: 3
Why:    The strings are identical so the whole string is a shared subsequence.

Input:  text1 = "abc", text2 = "def"
Output: 0
Why:    No letter of the first string appears anywhere in the second one, so no common subsequence exists.

Constraints

1 <= text1.length, text2.length <= 1000, both strings consist of lowercase English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Common Subsequence

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Common Subsequence. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.