0190MediumStringDynamic ProgrammingLongest Common Subsequence

Shared Checkpoint Order

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_shared_trace(logA: str, logB: str) -> int:

Java

public int longestSharedTrace(String logA, String logB)

The intended approach

Time O(n*m)Space O(min(n, m))

Compare prefixes of the two logs. If the next entry matches on both sides it can be appended to the best trace of the two shorter prefixes; if it does not, the best trace must already ignore one of the two entries, so take the better of dropping either. Only the row for the previous entry of one log is ever read, so two rolling rows over the shorter log replace the full table.

Pythonentry point: longest_shared_trace

def longest_shared_trace(logA, logB):
    # Time O(n*m): every prefix pair is scored once.
    # Space O(min(n, m)): two rolling rows over the shorter log.
    if len(logA) < len(logB):
        logA, logB = logB, logA
    width = len(logB)
    prev = [0] * (width + 1)
    for entry in logA:
        cur = [0] * (width + 1)
        for j in range(1, width + 1):
            if entry == logB[j - 1]:
                cur[j] = prev[j - 1] + 1
            elif cur[j - 1] >= prev[j]:
                cur[j] = cur[j - 1]
            else:
                cur[j] = prev[j]
        prev = cur
    return prev[width]

The obvious version

Enumerate every subset of the shorter log as a candidate trace and test whether it embeds in the longer log with a greedy scan. Exponential, 2^n candidates.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shared_trace(logA, logB):
    if len(logA) <= len(logB):
        short, long_ = logA, logB
    else:
        short, long_ = logB, logA

    def embeds(sub, whole):
        pos = 0
        for ch in sub:
            while pos < len(whole) and whole[pos] != ch:
                pos += 1
            if pos == len(whole):
                return False
            pos += 1
        return True

    n = len(short)
    best = 0
    for mask in range(1 << n):
        pick = [short[i] for i in range(n) if (mask >> i) & 1]
        if len(pick) > best and embeds(pick, long_):
            best = len(pick)
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in