LeetCode #5 Longest Palindromic Substring

Medium

Problem

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"

Solution

Iterate entire string once and expand palindrome as longer as possible.

Complexity

It’s clear that we only iterate entire string once. Although there is a max comparison but elements in candidates will not be more than three. Hence it takes O(n) time to iterating. Besides, the subroutine takes O(n) as well. Thus total time complexity is O(n²), where n denotes to the length of the given string.

It’s trivial that it only takes O(1) extra space.