Leetcode 5 - Longest Palindromic Substring

Prompt: Given a string, find the longest substring that is a palindrome.

Example:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Input: s = "ac"
Output: "a"

Solution: We can solve this by finding all possible palindromes by expanding left and right on each character. The condition for a substring to be a palindrome is that the starting character must be equal to the ending character. While we find all possible palindromes, we can also save the longest palindrome. The runtime for this solution is O(n²) since it loops through all characters and it expands to all other characters.