Answer:
Algorithm:
for (i = 0; i < n; i++)
L[i][i] = 1;
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
Time complexity:
O(n^2)
Explanation:
- Run a for loop until i is less than n and assign a value of 1 to the L 2D array which is of size n*n while n being the length of the string.
- Run a nested for loop and check if the value at ith and jth index of str input string is equal, and then assign the value of 2 to the L 2D array.
- Otherwise choose the maximum value from within the 2D array using the max function.
- As there is a nested loop used in this algorithm so the time complexity of the algorithm is O(n^2).
