# 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(intei = 0; ei < s.length(); ei ++)for(intsi = 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 …