"""Leetcode 5. Longest Palindromic Substring
Medium

Given a string s, find the longest palindromic substring in s. 
You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"
"""

class Solution(object):
	def longestPalindrome(self, s):
		"""
		:type s: str
        :rtype: str
		"""
		pass


def main():
	s = 'babad'
	print(Solution().longestPalindrome(s))

	s = 'cbbd'
	print(Solution().longestPalindrome(s))


if __name__ == '__main__':
	main()

@@ -298,16 +298,21 @@
 Solution
+Naive
 (object)
@@ -313,17 +313,20 @@
 bject):%0A
-%09
+    
 def long
@@ -349,24 +349,36 @@
 lf, s):%0A
-%09%09%22%22%22%0A%09%09
+        %22%22%22%0A        
 :type s:
@@ -406,16 +406,664 @@
 str%0A
-%09%09%22%22%22%0A%09%09
+%0A        Time limit exceeded.%0A        %22%22%22%0A        n = len(s)%0A        max_len = 1%0A        max_i = 0%0A        max_j = 0%0A        %0A        for i in range(n):%0A            for j in range(i + 1, n):%0A                if s%5Bi:(j + 1)%5D == s%5Bi:(j + 1)%5D%5B::-1%5D:%0A                    ij_len = j - i + 1%0A                    if ij_len %3E max_len:%0A                        max_len = ij_len%0A                        max_i = i%0A                        max_j = j%0A                else:%0A                    break%0A        return s%5Bmax_i:(max_j + 1)%5D%0A%0A%0Aclass SolutionDP(object):%0A    def longestPalindrome(self, s):%0A        %22%22%22%0A        :type s: str%0A        :rtype: str%0A        %22%22%22%0A        
 pass
@@ -1077,17 +1077,20 @@
 main():%0A
-%09
+    
 s = 'bab
@@ -1092,18 +1092,36 @@
  'babad'
-%0A%09
+    # Ans: bab.%0A    
 print(So
@@ -1118,32 +1118,37 @@
   print(Solution
+Naive
 ().longestPalind
@@ -1157,17 +1157,20 @@
 me(s))%0A%0A
-%09
+    
 s = 'cbb
@@ -1171,18 +1171,36 @@
 = 'cbbd'
-%0A%09
+     # Ans: bb.%0A    
 print(So
@@ -1205,16 +1205,21 @@
 Solution
+Naive
 ().longe
@@ -1268,9 +1268,12 @@
 _':%0A
-%09
+    
 main

Complete naive longest palindromic substring