Longest Palindromic Substring

---

2nd attempt: Longest Palindromic Substring 2023-04-14 11.25.48.excalidraw 1st attempt: Longest Palindromic Substring 2023-02-08 08.53.24.excalidraw

Temp

class Node:
    def __init__(self, val=None, index=-1, next=None):
        self.val = val
        self.next = next
        self.index = index
 
 
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
 
        llarr = []
 
        for i, c in enumerate(s):
            llarr.append(Node(val=c, index=i))
        
        #FIXME Unnecessary cycles herein
        for i in range(n):
            curNode = llarr[i]
            for j in range(i + 1, n):
                nextNode = llarr[j]
                if curNode.val == nextNode.val:
                    curNode.next = nextNode
                    curNode = nextNode
    
        i = 0
        j = 0
        longestSubstring = 0
        while i < n:
            j = llarr[i].next.index
            foundSubPattern = False
            for k in range(i + 1, j): # (i, j) inclusive
                if llarr[k].next:
                    length = llarr[k].index - i + 1
                    longestSubstring = max(length, longestSubstring)
                    i = j
                    j = llarr[j].index - i + 1
                    continue               
            
            i += 1

Next Try to Find the pattern

Longest Palindromic Substring

Iterative Solution

Recursive Solution (slow, timeout)

Leetcode 2023-01-13 17.46.06.excalidraw

from collections import deque  
  
def is_palindrome(s, n):  
    if n == 1:  
        return True  
    if n == 2:  
        return s[0] == s[1]  
  
    if n % 2 == 0:  
        mid = n // 2  
        left_part = s[0:mid]  
        right_part = s[mid:n]  
  
        return left_part == right_part[::-1]  
  
    i = 0  
    j = n - 1  
    while i != j:  
        if s[i] != s[j]:  
            return False  
        i += 1  
        j -= 1  
  
    return True  
  
  
class Solution:  
    def __init__(self):  
        self.longest_palindrome = ""  
        self.queue = deque()  
        self.longest_count = 0  
        self.dp = set()  
  
    def find_palindrome(self):  
        if len(self.queue) == 0:  
            return  
  
        s = self.queue.pop()  
  
        n = len(s)  
  
        # print(self.dp)  
  
        if n > self.longest_count:  
            if n <= 1 or is_palindrome(s, n):  
                self.longest_palindrome = s  
  
                self.longest_count = len(self.longest_palindrome)  
                return  
  
        if self.longest_palindrome and (len(self.queue[-1]) == (n - 1)):  
            return  
  
        if s not in self.dp:  
            self.dp.add(s)  
  
            left_substring = s[0:n - 1]  
            right_substring = s[1:n]  
  
            self.queue.appendleft(left_substring)  
            self.queue.appendleft(right_substring)  
  
        self.find_palindrome()  
  
    def longestPalindrome(self, s: str) -> str:  
        self.queue.append(s)  
        self.find_palindrome()  
  
        return self.longest_palindrome  
  
  
def main():  
    s = "eabcb"  
    solution = Solution()  
    res = solution.longestPalindrome(s)  
    print(res)  
  
  
if __name__ == "__main__":  
    main()

---

References

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