$5.$ The longest common subsequence problem is defined as follows:

Input: a string S$,$ consisting of n characters, and a string T consisting of m characters. Output: the length of the longest sequence of characters that appear in order from left to right $($but not necessarily consecutively$)$ in both S and T$.$ For example, suppose S$=$college and T $=$computerscience. Then a longest common subsequence $($SCS$)$ is SCEE, which has length $4$: CollEgE and computerSCiEncE Let LCS$($i$,$ j$)$ denote the length of the longest common subsequence of the first i characters in S and the first j characters in T $($where the first character has index $1).$

$($a$)$Give a recurrence that expresses LCS$($i$,$ j$)$ in terms of solutions to smaller

subproblems. Describe the base cases.

$($b$)$ What does it mean for a problem to have overlapping subproblems? How do we use this property when designing a dynamic programming algorithm?