A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm?

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).