# Python solution using binary search

• Use binary search for the length of palindromic string
use mid & mid2 because the length can be even or odd

``````class Solution(object):

def n_length_Pl(self, st, lth):
for i in range(len(st) - lth + 1):
sub_st = st[i:i+lth]
if sub_st == sub_st[::-1]:
return sub_st
return ""

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)

max_pl = ""

# use binary search
first = 0
last = l

while first <= last:

mid = (first + last) / 2

mid2 = min(l, mid + 1)

chk_pl1 = self.n_length_Pl(s, mid)
chk_pl2 = self.n_length_Pl(s, mid2)

if chk_pl1 == "" and chk_pl2 == "":
last = mid - 1
elif chk_pl1 != "" and chk_pl2 == "":
max_pl = chk_pl1
first = mid2 + 1
elif chk_pl2 != "":
max_pl = chk_pl2
first = mid2 + 1

return max_pl
``````

• I came up with the same concept (binary search), glad I'm not the only one xD
Pretty sure it's not linear, but it gets accepted, so should be below `O(n³)` -- and `O(1)` storage other than the answer itself.

I think it's something like `O(N² * log N)` (probably wrong..)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.