Generated by Codex with GPT-5

Quick facts

Problem gist

Given two strings, the task is to find the length of the longest sequence of characters that appears in both strings in the same relative order.

The characters do not need to be contiguous. For example, "ace" is a subsequence of "abcde" because a, c, and e appear in order, even though there are skipped characters between them.

So the question is not “what is the longest shared substring?” It is “how many characters can both strings keep if each is allowed to delete characters but not reorder the remaining ones?”

The useful way to think about it

At any point, compare a prefix of the first string with a prefix of the second string. The answer for those prefixes depends on the final characters:

  • If the final characters match, that character can extend a common subsequence from the two smaller prefixes.
  • If they do not match, the best answer must come from dropping one final character: either ignore the last character of the first prefix, or ignore the last character of the second prefix.

That gives a clean dynamic programming recurrence.

Let dp[i][j] mean the LCS length between text1[:i] and text2[:j].

If text1[i - 1] == text2[j - 1], then:

dp[i][j] = dp[i - 1][j - 1] + 1

Otherwise:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

The base case is simple: if either prefix is empty, the LCS length is 0.

Why the optimized version works

The full DP table has m * n states, where m and n are the string lengths. Each state only needs three nearby values:

  • the previous row, same column
  • the current row, previous column
  • the previous row, previous column

That means the full table is not necessary when the problem only asks for the length. Two rows are enough: keep the row for the previous character of the outer string, build the current row from left to right, then replace the previous row.

Using the shorter string as the column dimension keeps memory small without changing the answer, because LCS is symmetric.

Python solution

from typing import Tuple


def order_by_length(first_text: str, second_text: str) -> Tuple[str, str]:
    """Return the longer text first so the shorter text can be the DP row."""
    if len(first_text) >= len(second_text):
        return first_text, second_text
    return second_text, first_text


def longest_common_subsequence_length(first_text: str, second_text: str) -> int:
    if not first_text or not second_text:
        return 0

    outer_text, column_text = order_by_length(first_text, second_text)
    previous_row = [0] * (len(column_text) + 1)

    for outer_character in outer_text:
        current_row = [0] * (len(column_text) + 1)

        for column_index, column_character in enumerate(column_text, start=1):
            if outer_character == column_character:
                current_row[column_index] = previous_row[column_index - 1] + 1
            else:
                current_row[column_index] = max(
                    previous_row[column_index],
                    current_row[column_index - 1],
                )

        previous_row = current_row

    return previous_row[-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return longest_common_subsequence_length(text1, text2)

Time complexity is O(m * n) because every pair of prefix positions is considered once.

Extra space is O(min(m, n)) because only two rows over the shorter string are stored.

Interview follow-ups

How would you return one actual longest common subsequence, not just its length?

Use the full m * n DP table instead of two compressed rows. After filling the table, start at dp[m][n] and walk backward. When the two current characters match, include that character and move diagonally to i - 1, j - 1. When they do not match, move toward the neighbor with the larger DP value.

This works because the table stores the best LCS length for every prefix pair, so the backward walk can reconstruct one set of decisions that achieved the optimal length. The tradeoff is memory: returning the sequence directly usually costs O(m * n) space, though the time remains O(m * n).

Can this be done with one DP row instead of two?

Yes. A one-row solution stores dp[j] as the previous row’s value until it is overwritten, and keeps a temporary variable for the old diagonal value dp[j - 1]. On a match, the new value becomes old_diagonal + 1; on a mismatch, it becomes max(dp[j], dp[j - 1]).

The complexity is still O(m * n) time and O(min(m, n)) space. The tradeoff is readability. The two-row version is easier to explain because the recurrence maps directly to “previous row” and “current row.” The one-row version is useful when squeezing memory further matters, but it is easier to make an off-by-one mistake.

What if the interviewer asks for all longest common subsequences?

The DP length table still helps, but the output can be exponentially large. After building the table, a backtracking step can follow every optimal branch instead of choosing only one branch. When both neighbors preserve the same optimal length, both paths may need to be explored.

This is correct because the DP table identifies which moves can still lead to an optimal answer. The important complexity point is that no algorithm can list exponentially many subsequences in polynomial output time. A production version should use deduplication and should usually expose a limit or streaming interface instead of materializing every result blindly.

How would the answer change for longest common substring?

Longest common substring requires the shared characters to be contiguous. That changes the recurrence. When characters match, extend the diagonal value by one. When they do not match, reset the current cell to zero, because a contiguous match cannot survive a mismatch.

The time complexity is still O(m * n), and the memory can still be compressed. The key difference is the meaning of the state: LCS tracks the best subsequence over prefixes, while longest common substring tracks the length of a matching suffix ending at the current pair of positions.

Can the problem be improved when one string is very short?

The two-row DP already takes advantage of this by using the shorter string as the column dimension, so the extra space becomes proportional to the shorter input. The time remains O(m * n), though, because each character pair may still matter.

For special alphabets or very long texts, bitset-based dynamic programming can speed up the inner loop by processing many column positions in one machine word. That is a useful systems optimization, but it is more complex and less portable than the standard DP. In a normal interview, the compressed-row DP is the best default answer.