# 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 answerend`

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    resend`
`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    resend`
`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 longestend`

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.