5. Longest Palindromic Substring.md

https://leetcode.com/problems/longest-palindromic-substring/

1. testcase a aba abcba abcdcba

aa abba abccba abcddcba

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" for Idea 1, Need to decrease the computed time. "aaaabaaa" 2. Idea 2, start form tail, to find the same char, if find it, check the palindromic, if find break

for cur in 0..size
     for nxt in size..cur
         if (nxt - cur) <= (p_e - p_s)
             break;
         if str[cur] != str[nxt]
             continue;
         if palindromic_check()
             p_s = cur;
             p_e = nxt; 
             break;

Accepted solution

Success
Details
Runtime: 9276 ms, faster than 5.01% of Python3 online submissions for Longest Palindromic Substring.
Memory Usage: 14.4 MB, less than 38.84% of Python3 online submissions for Longest Palindromic Substring.

Source in Python3

def palindromic_chk (s: str, start: int, end: int):
    t = end
    for h in range(start, end + 1):
        #print("chk ", h, t) 
        if (h >= t):
            return True
        if s[h] != s[t]:
            return False
        
        t -= 1;
            
    return False


class Solution:
    def longestPalindrome(self, s: str) -> str:
        lngst_s = 0
        lngst_e = 0
        
        for cur in range(0, len(s)):
            #print("cur ", cur, "nxt ", nxt)
            for nxt in range(len(s) - 1, cur, -1):
                if (nxt - cur) <= (lngst_e - lngst_s):
                    break;
                if s[cur] != s[nxt]:
                    continue
                if palindromic_chk (s, cur, nxt):
                    lngst_s = cur
                    lngst_e = nxt
                    break;
                        
        #print(lngst_s, lngst_e) 
        return s[lngst_s:lngst_e + 1]

Idea 1, start from head, find next the same character

e.g. abba, start from a, find the next a, then check palindromic

for cur in 0..size
     for nxt in head+1..size
         if (size - cur) < (p_e - p_s + 1)
             break;
         if str[cur] != str[nxt]
             continue; 
         if palindromic_check()
             if (nxt - cur) > (p_e - p_s)
                 p_s = cur;
                 p_e = nxt; 
             continue;

3. palindromic check, there're two pointer, one point to head and another to tail. head ++, tail -- until head >= tail(palindromic).