5. 最长回文子串 https://leetcode-cn.com/problems/longest-palindromic-substring/

5.rb

# s[i..j]
# dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1, j - 1])

# @param {String} s
# @return {String}
def longest_palindrome(s)
  return s if s.size <= 1
  
  longest_size = 1
  longest_s = s[0]
  
  dp = Array.new(s.size){ Array.new(s.size) }
  
  (1..s.size).each do | j |
    (0...j).each do | i |
      if s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])
        dp[i][j] = true
        if (j - i + 1 > longest_size)
          longest_size = j - i + 1
          longest_s = s[i..j]
        end
      end
    end
  end
  longest_s
end