(Solved): Problem 3. Write pseudocode for an algorithm that accepts a string (or character array) str as its ...

Problem 3. 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. Example 1: If the input string is "abcabbadabc", then your algorithm should return "badab". Example 2: If the input string is "zyxxwvvu", then your algorithm should return "xx" or "vv". Example 3: If the input string is "abcde", then you algorithm may return any one of the following: "a", "b", "c", "d", or "e". Your algorithm should have best-case runtime of \( O(n) \) and worst case runtime of \( O\left(n^{2}\right) \). 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. Hint. The naive approach to this problem, which involves iterating over all possible starting and ending indices of substrings and then checking whether each substring is itself a palindrome runs in time \( \mathrm{O}(\mathrm{n} 3) \) and is not a correct solution to this problem.