Interview Questions/Coding/Shared Transcript LCS Count

Shared Transcript LCS Count

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Shared Transcript LCS Count

Two interview transcripts are represented as strings. A shared review sequence is any sequence of characters that can be read from both transcripts in order, without needing the characters to be contiguous. Among all shared review sequences, consider only those with maximum possible length. Different resulting strings count once, even if they can be formed through multiple index choices. Input Format: You are given two strings a and b. Output Format: Return the number of distinct longest common review sequences.

Examples

Example 1

Input:

a = "abcabcaa"
b = "acbacba"

Output:

Explanation: The longest common transcript length is 5. There are 7 distinct transcripts of that length after removing duplicates.

Approach hint

First compute the LCS length table.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp