← DiffPush

Longest Common Subsequence

Standard Bar Dynamic Programming · DP on Strings O(n*m) · O(min(n, m))

The Changelog Diff Anchor

A documentation tool compares two revisions of a protocol spec by finding the longest run of terms that appear in both versions in the same relative order — the anchor text both revisions share. Terms need not be adjacent, only in sequence. The diff viewer highlights that anchor length to visualize how much of the spec survived the edit.

Input: Two strings text1 and text2.

Output: Return the length of the longest sequence of characters appearing in both strings in the same relative order.

Constraints

• 1 <= len(text1), len(text2) <= 1000
• strings consist of lowercase English letters

Examples

Example 1

Input: {"text1":"abcde","text2":"ace"}
Output: 3
The shared in-order anchor is "ace" — length 3.

Example 2

Input: {"text1":"abc","text2":"def"}
Output: 0
No character appears in both strings.

Solve this in your browser →

Also on LeetCode ↗