Longest Subsequence of A That Is a Substring of B

Problem Statement

Given strings A and B, find the length of the longest subsequence of A that appears as a contiguous substring in B. A subsequence of A preserves the relative order of characters but may skip positions. A substring of B is a contiguous range of B.

Example 1:

Input: A = "abcde", B = "ace"
Output: 3
Explanation: "ace" is a subsequence of A (drop 'b' and 'd') AND a substring of B.

Example 2:

Input: A = "adbc", B = "abc"
Output: 3
Explanation: "abc" is a subsequence of A (a at 0, b at 2, c at 3) AND a substring of B.

Example 3:

Input: A = "xyz", B = "abc"
Output: 0
Explanation: No common characters.

Constraints:

• 0 <= A.length, B.length <= 1000.

Difficulty: Medium-Hard Round: OA

---

Pattern Recognition

• What is the input structure? Two strings.
• What are we optimizing? Max length of a string that is subsequence-of-A and substring-of-B simultaneously.
• What pattern does this fit? 2D DP on two strings — a hybrid between LCS (subsequence) and substring matching.
• Why does this pattern fit? The state (i, j) where i is a position in A and j is a position in B has overlapping subproblems. The twist vs standard LCS: the B side must be contiguous, so the DP state must encode "the candidate substring ends exactly at position j - 1 in B."

---

Approach

Brute Force — Try Every Substring of B

For every substring B[l..r], check whether it is a subsequence of A. Track the longest.

Time: O(m^2 * n) — O(m^2) substrings, each checked against A in O(n). Space: O(1). Why insufficient: For m = n = 1000, this is 10^9 ops — likely TLE.

Optimal — 2D DP

Key Insight: Define dp[i][j] = length of the longest subsequence of A[0..i-1] that equals a contiguous substring of B ending exactly at position j - 1. The "ending exactly" constraint keeps the B side contiguous.

Transitions:

• dp[i][j] = dp[i-1][j] — skip A[i-1] (don't include this character). This keeps the B-side ending fixed at j - 1.
• If A[i-1] == B[j-1], also try dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1) — take this character. Now the substring of B ending at j - 1 was previously ending at j - 2.

Answer: max(dp[n][j]) over all j.

Step-by-step:

1. Initialize a (n+1) x (m+1) table of zeros.
2. Iterate i from 1 to n, j from 1 to m.
3. Apply the transitions.
4. Scan the last row for the max.

Time: O(n * m). Space: O(n * m), reducible to O(m) with rolling rows.

---

Walkthrough

Trace on A = "adbc", B = "abc":

n = 4, m = 3. Initial dp is all zeros.

Process cell-by-cell:

i	j	A[i-1]	B[j-1]	equal?	dp[i-1][j] (skip)	dp[i-1][j-1] + 1 (take)	dp[i][j]
1	1	a	a	yes	0	0 + 1 = 1	1
1	2	a	b	no	0	—	0
1	3	a	c	no	0	—	0
2	1	d	a	no	1	—	1
2	2	d	b	no	0	—	0
2	3	d	c	no	0	—	0
3	1	b	a	no	1	—	1
3	2	b	b	yes	0	1 + 1 = 2	2
3	3	b	c	no	0	—	0
4	1	c	a	no	1	—	1
4	2	c	b	no	2	—	2
4	3	c	c	yes	0	2 + 1 = 3	3

Last row: [_, 1, 2, 3]. Max = 3.

Answer: 3 (the subsequence "abc" of A at positions 0, 2, 3 equals substring "abc" of B).

---

Implementation

TypeScript

function longestSubsequenceSubstring(A: string, B: string): number {
    const n = A.length, m = B.length;
    // dp[i][j]: longest subsequence of A[0..i-1] that is a substring of B ending at j-1.
    const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            // Skip A[i-1]: B substring still ends at j-1.
            dp[i][j] = dp[i - 1][j];
            // Take A[i-1] if it matches B[j-1]: previously ended at j-2.
            if (A[i - 1] === B[j - 1]) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }

    // Answer is the max over all ending positions in B.
    let best = 0;
    for (let j = 0; j <= m; j++) best = Math.max(best, dp[n][j]);
    return best;
}

C++

#include <string>
#include <vector>
#include <algorithm>

int longestSubsequenceSubstring(const std::string& A, const std::string& B) {
    int n = A.size(), m = B.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (A[i - 1] == B[j - 1])
                dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }

    int best = 0;
    for (int j = 0; j <= m; j++) best = std::max(best, dp[n][j]);
    return best;
}

Watch out:

1. Confusing with plain LCS. Plain LCS (LC 1143) lets both sides skip freely. Here only A can skip; B must be contiguous. The state must encode "ending at j-1."
2. Answer at dp[n][m]. Wrong — that only counts substrings ending at the very end of B. Scan the whole last row.
3. Missing the "skip A[i-1]" transition. Without dp[i][j] = dp[i-1][j], you lose valid subsequences that skip characters of A.

---

Complexity Analysis

	Time	Space
Brute Force	O(m^2 * n)	O(1)
Optimal DP	O(n * m)	O(n * m)
Space-Optimized DP	O(n * m)	O(m)

Bottleneck: The product of string lengths. For n = m = 1000, 10^6 ops — comfortable.

---

Edge Cases

1. Empty A or empty B — result is 0. The DP initializes to 0 and nothing updates.
2. No common characters — all transitions from "take" fail; result stays 0.
3. A contains B — answer is B.length.
4. B is a single character — answer is 1 if that character appears in A.
5. A == B — answer is A.length (trivially a substring of itself and a subsequence).

---

Related Problems

• LC 1143 — Longest Common Subsequence — Both sides can skip. Simpler transitions.
• LC 583 — Delete Operation for Two Strings — Uses LCS to compute min deletions.
• LC 718 — Maximum Length of Repeated Subarray — Both sides must be contiguous. Different transitions, same 2D DP shape.
• LC 1092 — Shortest Common Supersequence — LCS applied to merge.

---

OA Strategy Notes

This is a "heavy" OA problem — budget 30-40 minutes. The risk is conflating with plain LCS; reread the problem twice before coding. Write out the transition table before implementing. For 75-minute two-problem OAs, this is often problem 2.

---

What is Expected at Each Level

Junior: Recognizes 2D DP. May confuse the transitions with LCS. With a hint about "B must be contiguous," arrives at the correct recurrence.

Mid-level: Defines the state precisely ("ending at j-1"), writes correct transitions, scans the last row for the answer.

Senior: Space-optimizes to O(m). Discusses why the symmetric variant (subseq of A that is subseq of B — plain LCS) differs. Notes that "contiguous in B, non-contiguous in A" is a common real-world pattern (e.g., fuzzy match with anchor).