Write the stringAlignment(String x, String y) method.

Given two characters a and b, we define a function penalty (a, b) as follows: if a equals b, penalty (a, b) = 0. If a or b equals $ then penalty (a, b) = 4; otherwise penalty (a, b) = 2. Given two strings x = x_1 x_2 ...x_n and y = y_1 y_2 ... y_n alignment cost between x and y is AlignCost (x, y) = sigma^n_i = 1 penalty (x_i, y_i). Let x = x_1 x_2 ... x_n and y = y_1 y_2 ... y_m two string where n greaterthanorequalto m. assume that neither string has the character $. Our task is to align the two strings. The alignment is done by creating a new string z formed by inserting the character $ at n - m indices in y. Note that length of z is n. Note that there are many choices for z. The goal is to find a z for which AlignCost(x, z) is minimized. We would like to write a method that gets two strings x (of length n) and y (of length m) as parameters (assume that n greaterthanorequalto m) and computes a z such that AlignCost(x, z) lessthanorequalto AlignCost(x, z') for every z' (obtained by inserting n - m many $'s in y). Include the following static method in the class DynamicProgramming string Alignment (String x, String y). Assume that x is a string of length n and y is a string of length m such that n greaterthanorequalto m. This method returns a string z (obtained by inserting $ at n - m indices in y) such that AlignCost(x, z) lessthanorequalto AlignCost(x, z') over all possible z' (obtained by inserting n - m many $'s in y). You may assume that length of x is at least the length of y and neither of x or y has the character $. Note that the length of the returned string z must equal the length of x