_5. Longest Palindromic Substring.md

5. Longest Palindromic Substring

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Two Pointers, String, Dynamic Programming

Acceptance Rate : 34.126 %

---

Version 1 is severly inefficient since it checks each pair of indicies, reasulting in at least $O(n^2)$ runtime. On top of that, the inside of the nested loop has another for loop to check whether the substring is a palindrome. This would make the runtime increase further to a worst case leaning towards $O(n^3)$. While it does avoid redundant cases (i.e.) substrings of a length that wouldn't improve the current record, it's still a major negative.

Version 2 on the other hand avoids this by starting from the centre of each potential palindrome. It iterates through the string twice, once where it assumes the centre is a single character (and thus at least a palindrome of length $n$) and again where the indices $i$ and $i+1$ are used as the centre. In effect, it's checking odd and even length palindromes. This ends up being comfortably $O(n^2)$; a much greater improvement as compared to Version 1.

---

Solutions

• m5 v1 inefficient.py
• m5 v2 much better.py

Python

m5 v1 inefficient.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = 0
        longsetS = ''
        for i in range(len(s)) :
            for j in range(len(s) - 1, i - 1, -1) :
                if j - i + 1 <= longest :
                    continue
                isPal = True
                for k in range((j - i + 1) // 2) :
                    if s[i + k] != s[j - k] :
                        isPal = False
                        break
                if isPal :
                    longest = j - i + 1
                    longsetS = s[i: j+1]

        return longsetS

m5 v2 much better.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = 0
        longsetS = ''
        for i in range(len(s)) :
            currOffset = 1
            while 0 <= i - currOffset and \
                  i + currOffset < len(s) and \
                  s[i - currOffset] == s[i + currOffset] :
                currOffset += 1
            currOffset -= 1

            if longest < currOffset * 2 + 1 :
                longest = currOffset * 2 + 1
                longsetS = s[i - currOffset : i + currOffset + 1]

        for i in range(0, len(s) - 1) :
            currOffset = 0
            while 0 <= i - currOffset and \
                  i + currOffset + 1 < len(s) and \
                  s[i - currOffset] == s[i + currOffset + 1] :
                currOffset += 1

            if longest < currOffset * 2 :
                longest = currOffset * 2
                longsetS = s[i - currOffset + 1 : i + currOffset + 1]

        return longsetS