Longest Palindromic Substring

Category: Strings

Difficulty: Medium

Description

Write a function that, given a string, returns its longest palindromic substring.

A palindrome is defined as a string that's written the same forward and backward. Note that single-character strings are palindromes.

You can assume that there will only be one longest palindromic substring.

Sample Input

string = "abaxyzzyxf"

Sample Output

"xyzzyx"

Optimal Space & Time Complexity

O(n^2) time | O(n) space - where n is the length of the input string