Find longest common ordered restaurant list

You have two delivery drivers who each have a pickup plan represented as a list of restaurant IDs (strings).

Because there is only one car, the combined route can only visit restaurants that both drivers need to pick up from. The route must also respect the original order of restaurants for each driver (i.e., once you move forward in a driver’s list, you cannot go back).

Your task is to compute the longest possible list of restaurants that can be visited under these constraints.

Formally, given two sequences driver1 and driver2, return a sequence that is the longest common subsequence (LCS) of the two lists.

Input

• driver1: list of strings, length n
• driver2: list of strings, length m

Output

• A list of strings representing one longest common ordered restaurant list.

Notes

• The relative order must be preserved in both lists.
• If there are multiple valid longest answers, returning any one is acceptable (unless specified otherwise).

Example

• driver1 = ["A","B","C","D"]
• driver2 = ["B","C","E"]

A valid output is ["B","C"].

Constraints (reasonable interview assumptions)

• 0 <= n, m <= 2000 (adjust if needed)
• Restaurant IDs are case-sensitive strings

Follow-ups (optional)

• What is the time and space complexity of your approach?
• Can you optimize space if only the length is needed vs. reconstructing the sequence?

Find Longest Common Ordered Restaurant List

Hints

1. This is the classic Longest Common Subsequence problem — think of each driver's list as a sequence and find the longest ordered overlap.
2. Let dp[i][j] be the LCS length of driver1[i:] and driver2[j:]. If driver1[i] == driver2[j], then dp[i][j] = 1 + dp[i+1][j+1]; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j+1]).
3. After filling the table, reconstruct one actual subsequence by walking from (0, 0): on a match, take the element and advance both pointers; otherwise advance toward the larger dp value.