1047HardStringDynamic ProgrammingLongest Common Subsequence

The Shortest Tape Holding Both Readings

Tracked in this browser only

Trains the technique from

LeetCode 1092Shortest Common Supersequence

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 readings of lowercase letters are given, first and second. A tape holds a reading when deleting some of the tape's letters, possibly none of them, leaves that reading exactly.

Return the shortest tape that holds both readings. Where several tapes tie for shortest, return the one that comes first in dictionary order.

Examples

Example 1

Input: first = "bcd", second = "abc"
Output: "abcd"

The tape holds the first reading once its opening letter is dropped and the second once its closing letter is dropped. Nothing shorter works, since the two readings share only the letters b and c.

Example 2

Input: first = "abc", second = "def"
Output: "abcdef"

The two readings share no letter at all, so the tape has to hold all six. Writing the first reading before the second comes earlier in dictionary order than the other way round.

Example 3

Input: first = "ab", second = "ba"
Output: "aba"

Three letters are needed, since the readings share only one letter in common. Both possible tapes work, and the one opening on a comes first in dictionary order.

Constraints

1 <= first.length <= 1000
1 <= second.length <= 1000
Both readings are made of lowercase English letters.

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 shortest_common_supersequence(first: str, second: str) -> str:

Java

public String shortestCommonSupersequence(String first, String second)

The intended approach

Time O(m * n) for the table, then O(m + n) to read the tape off.Space O(m * n) for the table.

Work out, for every pair of places in the two readings, the length of the shortest tape holding what is left of each reading from those places on. With both readings used up the tape is empty. With one used up the tape is whatever remains of the other. Otherwise, if the two letters in hand match, the tape opens with that letter and both readings advance; if they differ, the tape opens with one of them and only that reading advances, so take whichever leaves the shorter tape. That table gives the shortest length. To read the tape itself off, walk forward from the start of both readings. Only two letters are ever worth writing at any point, the one in hand from each reading, since writing anything else lengthens the tape for nothing. Write the smaller of those two whose move keeps the length still to come at exactly what the table promises. Where the two letters match, both moves coincide and the two readings advance together. Taking the smallest workable letter at the earliest place it can be taken is what dictionary order asks for, and the table check is what stops an early small letter from lengthening the tape.

Pythonentry point: shortest_common_supersequence

def shortest_common_supersequence(first, second):
    m = len(first)
    n = len(second)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        table[i][n] = m - i
    for j in range(n + 1):
        table[m][j] = n - j
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if first[i] == second[j]:
                table[i][j] = 1 + table[i + 1][j + 1]
            else:
                a = table[i + 1][j]
                b = table[i][j + 1]
                table[i][j] = 1 + (a if a < b else b)
    out = []
    i = 0
    j = 0
    while i < m or j < n:
        if i == m:
            out.append(second[j])
            j += 1
            continue
        if j == n:
            out.append(first[i])
            i += 1
            continue
        want = table[i][j]
        best = None
        step = None
        moves = ((first[i], i + 1, j + 1 if second[j] == first[i] else j),
                 (second[j], i + 1 if first[i] == second[j] else i, j + 1))
        for letter, ni, nj in moves:
            if 1 + table[ni][nj] != want:
                continue
            if best is None or letter < best:
                best = letter
                step = (ni, nj)
        out.append(best)
        i = step[0]
        j = step[1]
    return "".join(out)

The obvious version

Search from the front of both readings instead. From a pair of places, either letter in hand may be written next, advancing that reading and the other one too when the letters match. Build the best tape from what follows and keep whichever choice gives the shorter tape, or the earlier one in dictionary order when they tie. Remember the answer for each pair of places so it is worked out once. Costs a stored tape per pair of places rather than a table of lengths and one walk.

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_shortest_common_supersequence(first, second):
    m = len(first)
    n = len(second)
    memo = {}
    def best(i, j):
        if i == m and j == n:
            return ""
        key = (i, j)
        if key in memo:
            return memo[key]
        if i == m:
            answer = second[j:]
        elif j == n:
            answer = first[i:]
        else:
            answer = None
            moves = ((first[i], i + 1, j + 1 if second[j] == first[i] else j),
                     (second[j], i + 1 if first[i] == second[j] else i, j + 1))
            for letter, ni, nj in moves:
                got = letter + best(ni, nj)
                if answer is None or len(got) < len(answer) or (len(got) == len(answer)
                                                                and got < answer):
                    answer = got
        memo[key] = answer
        return answer
    return best(0, 0)

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