Show problems as
Classic problem #1143MediumStringDynamic ProgrammingLongest Common Subsequence

Longest Common Subsequence

Real-world version: Shared Checkpoint Order
Tracked in this browser only
Read Longest Common Subsequence on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstOptimal Substructure · Dynamic Programming, animated step by step

Two field technicians walked the same plant during one shift. Each kept a personal log of the maintenance checkpoints they signed off, written in the order they signed them. Every checkpoint is identified by a single lowercase letter, and a technician may sign the same checkpoint again later in the shift.

Call a trace of a log whatever is left once you erase any number of its entries, including erasing nothing at all; the entries you keep stay in the sequence they were written.

Given the logs logA and logB, report how many entries the longest trace that occurs in both logs contains. Two logs that have no letter in common yield 0.

Examples

Example 1

Input
logA = "purge", logB = "urgent"
Output
4

Erase the leading `p` from the first log and you are left with `urge`; those same four checkpoints sit in that order inside `urgent`.

Example 2

Input
logA = "bolt", logB = "vein"
Output
0

The two technicians never touched the same checkpoint, so the longest trace they both hold is empty.

Example 3

Input
logA = "cot", logB = "carrot"
Output
3

All three entries of the first log reappear in order inside the second, even though `a` and the two `r` entries sit between them.

Constraints

  • 1 <= logA.length, logB.length <= 1000
  • logA and logB hold lowercase letters only

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_shared_trace(logA: str, logB: str) -> int:
Java
public int longestSharedTrace(String logA, String logB)

More on the same topics