"""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 SolutionNaive(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str

        Time complexity: O(n^3).
        Space complexity: O(1).
        """
        pal_s = ''

        for i in range(len(s)):
            for j in range(1, len(s) + 1):
                if s[i:j] == s[i:j][::-1] and j - i > len(pal_s):
                    pal_s = s[i:j]

        return pal_s


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

        Time complexity: O(n^3).
        Space complexity: O(n^2).
        """
        if not len(s):
            return ''

        n = len(s) - 1
        M = [[False] * (n + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            M[i][i] = True
            max_len = 1
            pal_s = s[i]
            
        for i in range(n):
            if s[i] == s[i + 1]:
                M[i][i + 1] = True
                max_len = 2
                pal_s = s[i:(i + 2)]

        for j in range(n + 1):
            for i in range(0, j - 1):
                if s[i] == s[j] and M[i + 1][j - 1]:
                    M[i][j] = True
                    if max_len < j - i + 1:
                        max_len = j - i + 1
                        pal_s = s[i:(j + 1)]
        return pal_s


def main():
    import time

    s = 'babad'    # Ans: bab.
   
    start_time = time.time()
    print('By naive: {}'.format(SolutionNaive().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By DP: {}'.format(SolutionDP().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))

    s = 'cbbd'     # Ans: bb.

    start_time = time.time()
    print('By naive: {}'.format(SolutionNaive().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By DP: {}'.format(SolutionDP().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))

    s = 'abcba'    # Ans: abcba

    start_time = time.time()
    print('By naive: {}'.format(SolutionNaive().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By DP: {}'.format(SolutionDP().longestPalindrome(s)))
    print('Time: {}'.format(time.time() - start_time))


if __name__ == '__main__':
    main()

@@ -808,32 +808,132 @@
    :rtype: str%0A%0A
+        Apply dynamic programming with botton-up memoization,%0A        but track longest palindrom.%0A%0A
         Time com
@@ -937,33 +937,33 @@
 complexity: O(n%5E
-3
+2
 ).%0A        Space
@@ -1059,20 +1059,16 @@
 = len(s)
- - 1
 %0A       
@@ -1068,17 +1068,17 @@
         
-M
+T
  = %5B%5BFal
@@ -1083,23 +1083,17 @@
 alse%5D * 
-(n + 1)
+n
  for _ i
@@ -1101,20 +1101,16 @@
  range(n
- + 1
 )%5D%0A%0A    
@@ -1121,36 +1121,32 @@
 for i in range(n
- + 1
 ):%0A            M
@@ -1140,25 +1140,25 @@
             
-M
+T
 %5Bi%5D%5Bi%5D = Tru
@@ -1175,19 +1175,17 @@
     
-max_len = 1
+start = i
 %0A   
@@ -1197,20 +1197,19 @@
     
-pal_s = s%5Bi%5D
+max_len = 1
 %0A   
@@ -1234,32 +1234,36 @@
 for i in range(n
+ - 1
 ):%0A            i
@@ -1294,25 +1294,25 @@
             
-M
+T
 %5Bi%5D%5Bi + 1%5D =
@@ -1337,19 +1337,17 @@
     
-max_len = 2
+start = i
 %0A   
@@ -1363,28 +1363,19 @@
     
-pal_s = s%5Bi:(i + 2)%5D
+max_len = 2
 %0A%0A  
@@ -1399,13 +1399,12 @@
 nge(
-n + 1
+2, n
 ):%0A 
@@ -1433,20 +1433,16 @@
 nge(0, j
- - 1
 ):%0A     
@@ -1472,17 +1472,17 @@
 %5Bj%5D and 
-M
+T
 %5Bi + 1%5D%5B
@@ -1509,17 +1509,17 @@
         
-M
+T
 %5Bi%5D%5Bj%5D =
@@ -1551,27 +1551,27 @@
  if 
-max_len %3C j - i + 1
+j - i + 1 %3E max_len
 :%0A  
@@ -1596,27 +1596,17 @@
     
-max_len = j - i + 1
+start = i
 %0A   
@@ -1630,28 +1630,28 @@
     
-pal_s = s%5Bi:(j
+max_len = j - i
  + 1
-)%5D
+%0A
 %0A   
@@ -1662,21 +1662,42 @@
  return 
-pal_s
+s%5Bstart:(start + max_len)%5D
 %0A%0A%0Adef m

Enhance DP ver by not tracking pal