Longest Palindromic Substring (in Python)

Problem

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

Solution

Make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions. For example, S="aba" is a palindrome, S="abc" is not.

---

Approach 1 : Brute Force

The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.

Complexity analysis

•Time complexity :  O(n3). Assume that n is the length of the input string, there are a total of 

$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$  such substrings (excluding the trivial solution where a character itself is a palindrome). Since verifying each substring takes O(n) time, the run time complexity is

$O(n^3)$.

•Space complexity : O(1).

---

Approach 2 : Expand Around Center

class Solution:
    def longestPalindrome(self, s):
 
        if len(s) < 1 :
            return ""
 
        start, end = 0, 0
 
        for i in range(len(s)) :
 
            # center의 갯수가 홀수인 경우 palindrome의 길이
            len1 = expandAroundCenter(s, i, i)
            # center의 갯수가 짝수인 경우 palindrome의 길이
            len2 = expandAroundCenter(s, i, i+1)
 
            x = max(len1, len2)
 
            # 현재 단어보다 길다면 start와 end를 바꿔줌.
            if (x > end - start) :
                start = i - (x-1)//2
                end = i + x//2
        
        return s[start:end+1]
 
def expandAroundCenter(s, left, right) :
 
    L, R = left, right
 
    while L>=0 and R<len(s) and s[L] == s[R] :
        L -= 1
        R += 1
    
    # 원래 길이보다 2만큼 길기 때문에.
    return R-L-1

Complexity Analysis

• Time complexity : $$O(n^2). Since expanding a palindrome around its center could take $$O(n)time, the overall complexity is $$O(n^2).

• Space complexity : $$O(1). 

Source : https://leetcode.com/problems/longest-palindromic-substring/