Programming Question : Leetcode-5

Today I have solved leetcode question5 — Longest Palindromic Substring .

Approach — 1) Brute Force — in this method , we just get each of the substrings of given string , see if it is a palindrome and if it is biggest palindrome, change the results’ value with it and return it in the end.

Time complexity of problem will be o(n³) and space complexity will be o(1)

2) Better Approach — in second approach, idea is that , for each letter in the string, we will assume that letter as middle element and look at its left and right if it is forming a palindromic substring and then get the substring.

in even strings, there can be two same letters in middle (like ‘caab’) so we will have to follow approach for two letters as well.

then we will return the palindromic substring or its length accordingly.

Time and Space complexities will be o(n²) and o(1).

Python Code:

class Solution(object):
def longestPalindrome(self, s):
#start from middile and look left and right
def helper(l,r):
while l>=0 and r<len(s) and s[l] == s[r]:
l-=1
r+=1
return s[l+1:r]

res=””
for i in range(len(s)):
temp = helper(i,i)
if len(temp) > len(res):
res= temp

temp = helper(i,i+1)
if len(temp) > len(res):
res= temp

return res