Longest Common Subsequence

For subtask $1$, enumerate every subsequence of $A$ and check whether it is a subsequence of $B$. This takes $O(2^N(N+M))$ time.

For the full problem, let $D_{i,j}$ be the length of a longest common subsequence of the first $i$ elements of $A$ and the first $j$ elements of $B$. Set . If , then . Otherwise, .

Backtrack from $D_{N,M}$. If the current elements match, add that element to the answer and decrease both indices. Otherwise, move to a preceding state with the same DP value. Reverse the collected elements to obtain an answer. If both preceding states have the same value, either choice works.

The time and space complexity are both $O(NM)$ per case.

Solution written by GPT6