Least Common Subsequence | Dataford Interview Questions

Your question is Least Common Subsequence. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Salesforce Metadata API tools may produce two ordered sequences of component names from different org versions. Given two strings, compute the length of their longest common subsequence, where matching characters must appear in the same order but do not need to be contiguous.

A subsequence can be formed by deleting zero or more characters without changing the order of the remaining characters. Return only the maximum possible length. This is the standard interpretation of the extracted “Least Common Subsequence” question.

Formal Specification

Implement longest_common_subsequence(text1, text2).

Input: Two strings text1 and text2 containing lowercase English letters.
Output: An integer representing the length of their longest common subsequence.
Characters may be skipped from either string, but their relative order must remain unchanged.

Constraints

0 <= len(text1), len(text2) <= 1000
text1 and text2 contain only lowercase English letters
The output is the length of the longest common subsequence

Function Signature

def longest_common_subsequence(text1, text2):