Algorithm Puzzles ~~everyday~~ ~~every week~~ sometimes: Longest Palindromic Substring

## Puzzle

Puzzle from leetcode:

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”

## Solving

### First Came out solution:

1 | class Solution { |

Result:

Well, that’s the worst result I have ever seen.

## Extend from the center

Checked the solution provided by leetcode, there is one way only have time complexity O(n²), I implemented in it C++ with a little optimization:

1 | class Solution { |

Result with this: