You are given the pickup job lists for two dashers who want to dash together in one car. Each list is an ordered list of merchant names. The dashers must respect the original left-to-right order of pickups in their own lists, but they are allowed to skip some pickup jobs.

Your task is to find the longest sequence of pickups that both dashers can complete together while preserving order in both lists.

For example, it is valid to go from "walmart" to "mcdonalds" if both dashers can do so in that order, but once they skip jobs in between, those skipped jobs cannot later be used.

This is an in-memory sequence problem. You only need to compute the best common pickup sequence from the two ordered pickup lists.

Method Signatures

List<String> longestPickupSequence(List<String> dasher1Pickups, List<String> dasher2Pickups)

• Returns the longest valid pickup sequence that appears in both lists in the same relative order.
• Two pickups match only if their merchant names are exactly equal.
• The returned sequence must preserve the original order from both input lists.
• If multiple longest valid sequences exist, return the lexicographically smallest sequence when compared element by element as strings.

Rules

• The dashers move from left to right in their own pickup lists.
• They may skip any number of pickup jobs.
• They cannot rearrange pickup jobs.
• A pickup can be used at most once from each list.
• Matching is case-sensitive and based on exact string equality.

Constraints

• 1 ≤ dasher1Pickups.size(), dasher2Pickups.size() ≤ 200
• 1 ≤ merchantName.length() ≤ 50
• Each merchant name is non-blank.
• Merchant names may repeat.
• Merchant names may contain lowercase English letters and spaces.

Return Value

• Return a List<String> containing the merchant names in the longest sequence the two dashers can complete together.
• If no common pickup exists, return an empty list.

Examples

Example 1

longestPickupSequence( dasher1Pickups = List.of("chillis", "albertsons", "walmart", "albertsons", "chillis", "mcdonalds", "burger king"), dasher2Pickups = List.of("chillis", "walmart", "chillis", "albertsons", "burger king", "applebees", "mcdonalds") )

Returns: List.of("chillis", "walmart", "albertsons", "burger king")

• This sequence appears in both lists in the same relative order.
• The maximum valid length is 4.
• Another length-4 sequence such as ["chillis", "walmart", "chillis", "mcdonalds"] also exists.
• By the tie-break rule, return the lexicographically smaller sequence.

Example 2

longestPickupSequence( dasher1Pickups = List.of("subway", "tacobell", "kfc", "subway"), dasher2Pickups = List.of("subway", "kfc", "subway") )

Returns: List.of("subway", "kfc", "subway")

• The sequence uses the first "subway", then "kfc", then the later "subway".
• All matches preserve left-to-right order in both lists.

Example 3

longestPickupSequence( dasher1Pickups = List.of("wendys", "chipotle"), dasher2Pickups = List.of("panera", "five guys") )

Returns: List.of()

• There is no common merchant name in the two pickup lists.

Example 4

longestPickupSequence( dasher1Pickups = List.of("a", "b", "c"), dasher2Pickups = List.of("a", "c", "b") )

Returns: List.of("a", "b")

• The longest valid length is 2.
• Two longest sequences are possible: ["a", "b"] and ["a", "c"].
• By the tie-break rule, return the lexicographically smaller sequence, which is ["a", "b"].