Longest Palindromic Substring

The text of the exercise is the following:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

**Example 1:**
Input: “babad"
Output: “bab"
Note: “aba” is also a valid answer.

**Example 2:**
Input: “cbbd"
Output: “bb"