Longest Common Subsequence | Dataford Interview Questions

Your question is Longest 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

Meta may compare text from Facebook, Instagram, or WhatsApp to identify shared ordered content patterns. Given two strings, return one longest common subsequence, preserving character order while allowing characters to be skipped.

A subsequence does not need to be contiguous. If multiple longest common subsequences exist, return any one of them.

Formal Specification

Implement longest_common_subsequence(text1, text2).

Input: Two strings text1 and text2 containing lowercase English letters.
Output: A string that is a longest common subsequence of text1 and text2.
The returned string must appear in both inputs in the same order, and no longer valid common subsequence may exist.

Constraints

0 <= len(text1), len(text2) <= 1000
Both inputs contain English letters
The result may be empty
Any valid longest common subsequence is accepted

Function Signature

def longest_common_subsequence(text1, text2):