A fully bracketed expression (FBE) is a string S over the characters (, ) that is either 1. the empty string, 2. the string TT or (T), where T is a fully bracketed expression, or 3. the string TU, where T and U are fully bracketed expressions. C 1C For example, the following are fully bracketed expressions: but the following are not: A sequence x = x2 . . . xn of brackets and parentheses is given to you (ie, ai E {G), [.])) and your goal is to find the shortest possible fully bracketed expression y that contains the given sequence z as a subsequence (not necessarily a contiguous substring). For example, if you are given (Il then both y = ( ) [ ] and y-([]) are shortest valid solutions. Give an efficient dynamic programming algorithm that takes the sequence z and computes the length of the shortest possible FEB y that contains a as a subsequence. Prove your algorithm is correct and analyze its running time. Hint: One successful approach involves letting oPT(i,j) stand for the length of the shortest FBE that contains .. as a subsequence. Note that in the shortest FBE containing r..zy, z is either "matched" to an appropriate character xk with i + 1 K , or it is not. If the former, then OPT(i,j). If the latter, then OPT(i,j) =