Question $3$: Longest Common Subsequence $(10$ points$)$

Given two strings, S$1$ and S$2,$ the task is to find the length of the Longest Common Subsequence $($LCS$),$ i$.$e$.$ longest

subsequence present in both of the strings. For example, for S$1=$AGGTAB$,$ S$2=$GXTXAYB$$

the output is $4,$ as the LCS is $$GTAB$.$ For S$1=$BD$,$ S$2=$ABCD$,$ the output is $2$ as the LCS is $$BD$.$

$1)$ Please design an efficient algorithm to solve the LCS$.$ What$$s its time complexity?

$2)$ Can you augment the algorithm to not only print out the length of the LCS$,$ but also the LCS itself?