Write pseudocode for an algorithm that accepts a string (or character array) str as its input and returns the longest substring of str that happens to be a palindrome. Recall that a palindrome is a string that, when reversed, equals itself. Examples of palindromes include "dad", "abcdededcba", "m", "ii", and "noon." If a string contains multiple palindrome substrings of maximal length, then your algorithm may return any of these substrings. Your algorithm should have best-case runtime of O(n) and worst case runtime of O(n^2). Your algorithm should use constant O(1) storage. Given an example of a string that yields best-case performance and an example of a string that yields worst case performance