Leetcode 5. Longest Palindromic Substring

Question

Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analyse

My first try using brute force method. and apparently, I get Time Limit Exceeded.

# @param {String} s
# @return {String}
def longest_palindrome(s)
answer = ""
return "" if s.eql? ""

for len in 1..s.length
for i in 0..s.length-len-1
flag = true
for si in 0..len/2
unless s[i+si].eql? s[len+i-si]
flag = false
break
end
end
answer = s[i..len+i] if flag
end
end
answer = s[s.length-1] if answer.eql? ""
return answer
end

We need to reduce time. Let’s try dynamic programming. I couldn’t write dynamic programming very well past. But I need to overcome my fear to be a better developer

2-D dynamic programming

We can focus on the start index si and end index ei. The longest string in substring is will be the longest string in the bigger substring. So we can focus on “ Is s[si..ei] a palindromic ”, we can just check if s[si-1..ei+1] a palindromic and if s[si].eql(s[ei]). If both the condition fits, we can get a positive answer. Then we can follow this order of loop to check all possible answer:

for(int ei = 0; ei < s.length(); ei ++)
for(int si = ei; si >= 0; si — )

And we can solve this question in O(n²) time complexity.

def longest_palindrome(s)  
map = {}
max_si, max_ei, max_length = nil, nil, 0
s.length.times do |ei|
si = ei
while si >= 0 do
if si == ei
map[ei] = { si => true }
else
map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
end

len = (ei - si + 1)
if map[ei][si] && len > max_length
max_length = len
max_si = si
max_ei = ei
end

si -= 1
end
end

s[max_si..max_ei]
end

This code from LeetCode题目:Longest Palindromic Substring,二维动态规划, unfortunately this code can’t pass Time Limit. Maybe Leetcode add new inputs in these years.

Expand from center

This is another solution with also O(n²) time complexity. We can assume all the index could be the center of palindromic in odd counts string, and all the intervals between index could be center in even counts string. Then we have to try O(n) times. and expands center cost O(n), so we can get the answer in O(n²).

# @param {String} s
# @return {String}
def odd_extend(s, c)
res = ""
for i in 1..c
unless s[c-i] == s[c+i]
break
else
res = s[(c-i)..(c+i)]
end
end
res
end
def even_extend(s, c) # center in even we define at the first floor index on left
res = ""
for i in 1..c+1
unless s[c-i+1] == s[c+i]
break
else
res = s[(c-i+1)..(c+i)]
end
end
res
end
def longest_palindrome(s)
longest = ""
if s.eql? ""
return ""
end

s.length.times do |c| # c for center
odd = odd_extend(s, c)
if odd.length > longest.length
longest = odd
end

even = even_extend(s, c)
if even.length > longest.length
longest = even
end
end

if longest == ""
longest = s[s.length-1]
end
return longest
end

This version still get Time Limit Exceeded, but it stop by 89 / 94 test cases. Reduce many time but still not enough.

def expand(s, center)  
li, ri = center.floor, center.ceil
if li == ri
li -= 1
ri += 1
end
left_space = li
right_space = s.length - ri - 1
max_space = [left_space, right_space].min
most_left = li - max_space
while li >= most_left do
if s[li] == s[ri]
li -= 1
ri += 1
else
break
end
end
[ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
i = 0
max_si, max_ei, max_len = nil, nil, 0
while i <= s.length - 1 do
len, si, ei = expand(s, i)
if max_len < len
max_si, max_ei, max_len = si, ei, len
end
i += 0.5
end
s[max_si..max_ei]
end

This Accepted code is from LeetCode题目:Longest Palindromic Substring,二维动态规划, maybe the difference with mine of performance is between For loop and While. So I tried to restruct my code with while, iterator. Improved a little bit performance, but just from 88/94 cases passed to 89/94. Then I thought maybe is cause by method calling. But when I move the method job into main method, the passed cases regressed to 88/94.

I still don’t know why, but I believe it will answer in future questions. Keep going …

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.