How to print Longest Common Subsequence?

Problem Statement

Given 2 strings, the task is to find longest common subsequence occurring in same order in both strings.

Subsequence can be obtained by deleting some or none of the elements from given sequence without changing their order.

Input s1: “abcde”  s2: “ace”  Output: 3  Explanation: Longest sequence is "ace" of length 3.

Example

This method checks for every subsequence of sequence S1 whether it also appears in sequence S2. S1 and S2 are two sequences with n and m lengths, respectively.    LCS( S1[1…m-1],S2[1….n]),LCS(S1[1…m],S2[1…..n-1])).

Simple Approach Solution

Time complexity: O(2^(n+m))    Space complexity: O(1)

Complexity of Simple Approach

It allows us to compute a problem, store the optimal solution, and then reuse it to avoid repeated executions.   DP[i][j] state: Longest sequence using starting i characters in S1 and starting j characters in S2.

Dynamic Programming Approach

Time complexity: O(nm)  Space complexity: O(nm)

Complexity of Dynamic Approach

Time complexity: O(nm)  Space complexity: O(nm)

Complexity of Dynamic Approach

How to implement the solutions in different languages?