Abstract / Summary

Find the shortest string that contains two given strings as subsequences.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (400k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes a shortest common supersequence (SCS) of two input strings. It follows a two-phase strategy: first it extracts the longest common subsequence (LCS) using a space-efficient dynamic programming routine, then it merges the original strings around the characters of the LCS to produce the final supersequence. The algorithm works entirely with Python strings and list containers, avoiding external libraries.

Phase 1 - Longest Common Subsequence Extraction

The core of the first phase is a dynamic programming table that records the LCS built so far for each prefix pair of the two strings. Instead of allocating a full two-dimensional matrix, the code keeps only the previous row and the current row, thereby reducing memory usage.

size1 = len(str1)
size2 = len(str2)

previous = [ "" ] * (size2 + 1)
for i in range(1, size1 + 1):
    current  = [ "" ] * (size2 + 1)
    for j in range(1, size2 + 1):
        if str1[i - 1] == str2[j - 1]:
            current[j] = previous[j - 1] + str1[i - 1]
        else:
            if len(current[j - 1]) >= len(previous[j]):
                current[j] = current[j - 1]
            else:
                current[j] = previous[j]
    previous = current
common = current[-1]

The inner loop compares the current characters of str1 and str2. When they match, the character is appended to the LCS of the previous diagonal cell. When they differ, the longer of the left and upper cells is propagated forward. By the end of the outer loop, current[-1] holds the LCS for the full strings.

Edge Cases Handled in Phase 1

• Empty input strings - When either str1 or str2 is empty, size1 or size2 becomes zero. The outer or inner loop runs zero times, leaving previous (or current) as a list of empty strings. Consequently common resolves to an empty string, which correctly represents the LCS of an empty string with any other string.
• No common characters - If the two strings share no characters, the condition str1[i - 1] == str2[j - 1] never triggers. The algorithm repeatedly selects the longer of the left and upper cells, which are all empty, so common remains empty. This outcome is appropriate because the LCS length is zero.
• Repeated characters - The DP logic naturally accommodates repeated characters because each cell reflects the best LCS for the corresponding prefixes. When a character appears multiple times, the algorithm chooses the earliest alignment that yields the longest subsequence.

Phase 2 - Greedy Merging Using the LCS

Having obtained the LCS, the second phase walks through each character of common. For each character, it extracts the leading segment of str1 up to the first occurrence of that character, appends it to the result, then discards the processed part of str1. The same operation is performed on str2. Finally, the common character itself is appended. After processing all characters of the LCS, any remaining suffixes of str1 and str2 are concatenated.

result = ""
for c in common:
    one = str1.find(c)
    result += str1[: one]
    str1    = str1[one + 1 :]

    two = str2.find(c)
    result += str2[: two]
    str2    = str2[two + 1 :]

    result += c

return result + str1 + str2

The find method returns the index of the first occurrence of the current LCS character in the remaining portion of each string. By slicing up to that index, the code captures all characters that must appear before the shared character in the supersequence. After the loop, any characters that were never part of the LCS are appended in their original order, guaranteeing that both input strings appear as subsequences of the result.

Edge Cases Handled in Phase 2

• Empty LCS - When common is empty, the loop body never executes. The final return statement concatenates the untouched str1 and str2, which is precisely the shortest supersequence when there is no overlap.
• LCS characters at the start of a string - If a common character is the first character of the remaining str1 or str2, find returns zero, and the slice str1[:0] (or str2[:0]) yields an empty string. The algorithm correctly adds no extra characters before the common character.
• Multiple occurrences of a common character - Because find always selects the first occurrence in the current suffix, the algorithm respects the order of characters in each original string. This ensures that the constructed supersequence does not reorder characters, preserving subsequence validity.
• Remaining suffixes after the last LCS character - After the loop, any characters that follow the final LCS character in either string are still present in str1 or str2. The concatenation result + str1 + str2 appends these trailing parts, handling the case where one string ends earlier than the other.

Performance Optimizations

The implementation incorporates several techniques that reduce resource consumption and improve runtime behavior:

• Row-wise DP storage - By retaining only two one-dimensional arrays (previous and current), the algorithm avoids the quadratic memory overhead of a full DP matrix. This is especially beneficial for long input strings, where the number of rows can be large.
• String concatenation via += on a growing result - The result string is built incrementally using +=. In CPython, repeated concatenation of short strings is optimized through an internal buffer, making this approach efficient for the typical sizes encountered in algorithmic problems.
• Use of str.find for locating LCS characters - The find method is implemented in C and runs quickly. By calling it only once per LCS character for each input string, the code minimizes the number of scans over the remaining suffixes.
• Avoidance of intermediate data structures - The merging phase works directly on the original strings, reassigning sliced views after each character is processed. This eliminates the need for auxiliary lists or queues, keeping the memory footprint low.

Overall, the solution balances clarity with practical efficiency, delivering a correct shortest common supersequence while employing space-saving DP and leveraging built-in string operations for fast processing.

Imagine two long trains made of alphabet blocks. You want to build one super train that includes all the blocks from both of those trains, but you want to keep it as short as possible.

The code first looks at both trains to see which blocks are exactly the same and in the same order. It keeps a list of these matching blocks to use as signposts along the way.

Once those signposts are found, the code starts building a new, combined train. It looks at the first train and grabs all the blocks that come before the first signpost, then it does the same for the second train. It adds all those blocks into the new train and then adds the matching signpost block itself. It keeps doing this for every signpost it found.

Finally, after all the matching blocks are used, there might be a few leftover blocks at the very end of the first train or the second train. The code just attaches those remaining blocks onto the end of the new train to make sure every single block from the beginning is part of the final, super-long train.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java	Python			Go	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	Dijkstra-Edu			Java
	everthis		JS
	fsq	C++
	Garvit244				Python
	JoshCrozier		JS
	lzl124631x	C++
	Shamik07					Dart
	sonugiri1043	C++
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
lzl124631x	C++
Shamik07	Dart
sonugiri1043	C++
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality