Longest Shared Thread

Medium

A subsequence of a string is what remains after crossing out any number of its characters (possibly none) while keeping the rest in their original order. For example, "tea" is a subsequence of "theatre", but "eat" is not. You are given two strings, first and second. Find the length of the longest string that is a subsequence of both. If they share no characters, return 0.

Example 1

first="bicycle", second="circle" → 4

One longest shared subsequence is "icle": the letters i, c, l, e appear in this order in both strings. There is no way to line up five shared letters.

Example 2

first="kayak", second="kayak" → 5

The strings are equal, so the whole string is shared, length 5.

Example 3

first="xyz", second="abc" → 0

There are no common letters, so the answer is 0.

Constraints

1 ≤ first.length, second.length ≤ 1000
Both strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium

Input

first="bicycle", second="circle"

Expected

Run checks the first 3 tests in your browser. Submit checks all 141 tests on the server, hidden ones included.