[LeetCode] 0005. Longest Palindromic Substring

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Table of contents

Python

				
					# time complexity: O(n) # space complexity: O(n) # Manacher's Algorithm class Solution: def longestPalindrome(self, s: str) -> str: sPrime = "#" + "#".join(s) + "#" n = len(sPrime) palindromeRadii = [0] * n center = radius = 0 for i in range(n): mirror = 2 * center - i if i < radius: palindromeRadii[i] = min(radius - i, palindromeRadii[mirror]) while ( i + 1 + palindromeRadii[i] < n and i - 1 - palindromeRadii[i] >= 0 and sPrime[i + 1 + palindromeRadii[i]] == sPrime[i - 1 - palindromeRadii[i]] ): palindromeRadii[i] += 1 if i + palindromeRadii[i] > radius: center = i radius = i + palindromeRadii[i] maxLength = max(palindromeRadii) centerIndex = palindromeRadii.index(maxLength) startIndex = (centerIndex - maxLength) // 2 longestPalindrome = s[startIndex: startIndex + maxLength] return longestPalindrome # Brute Force # time complexity: O(n^3) # space complexity: O(n^3) class Solution: def longestPalindrome(self, s: str) -> str: def check(i, j): left = i right = j - 1 while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True for length in range(len(s), 0, -1): for start in range(len(s) - length + 1): if check(start, start + length): return s[start: start + length] return "" # time complexity: O(n^2) # space complexity: O(n^2) # Dynamic Programming class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = [0, 0] for i in range(n): dp[i][i] = True for i in range(n-1): if s[i] == s[i+1]: dp[i][i+1] = True ans = [i, i+1] for diff in range(2, n): for i in range(n - diff): j = i + diff if s[i] == s[j] and dp[i+1][j-1]: dp[i][j] = True ans = [i, j] i, j = ans return s[i:j+1] s = "babad" print(Solution().longestPalindrome(s)) s = "cbbd" print(Solution().longestPalindrome(s))

Python

related articles