Longest Palindromic Substring
Given a string s, determine the longest palindromic substring in s. A substring is considered a palindrome if it reads the same forward and backward.
A substring is a contiguous sequence of characters within a string. The longest palindromic substring is the substring with the maximum length that satisfies this condition.
Examples
Input: "abacc" Output: "aba" Explanation: "aba" is longer than "cc"
Our solution finds the longest palindromic substring by expanding around potential centers in the input string. For each character in the string, we consider it as the center of a palindrome and expand outwards to determine the maximum length of the palindrome centered at that position. We repeat this for both odd-length and even-length palindromes.
- For each character, we use a helper function
expandAroundCenterthat takes two indices (leftandright) and expands outwards as long as the characters at these indices are equal and within the bounds of the string. - We calculate the lengths of palindromes centered at the current character (odd-length palindromes) and between the current character and the next one (even-length palindromes).
- We track the starting and ending indices of the longest palindromic substring found so far.
By comparing the lengths of the palindromes found in each iteration, we can determine the longest palindromic substring.
The use of expansion around centers ensures that we examine all potential palindromes efficiently.
def longest_palindromic_substring(s: str) -> str:
def expand_around_center(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
longest = ""
for i in range(len(s)):
# Odd length palindromes (single character center)
odd_palindrome = expand_around_center(i, i)
if len(odd_palindrome) > len(longest):
longest = odd_palindrome
# Even length palindromes (two character center)
even_palindrome = expand_around_center(i, i + 1)
if len(even_palindrome) > len(longest):
longest = even_palindrome
return longestTime Complexity: The solution has a time complexity of O(n^2), where n is the length of the input string. This is because, for each character in the string, we potentially expand outwards in both directions, resulting in quadratic time complexity in the worst case.
Space Complexity: The solution uses O(1) space beyond the input string. The only extra space used is for a few variables, making it very space-efficient.
Check out our lesson on the two-pointer approach to learn more about what it is and how to use it!
function isPalindrome(s, start, end) { while (s[start] === s[end] && end >= start) { start++; end--; } return end <= start; } function longestPalindromicSubstring(s) { let longestPalindrome = ''; for (let i=0; i < s.length; i++) { let j = s.length-1; while (s[i] !== s[j] && i <= j) { j--; } if (s[i] === s[j]) { if (isPalindrome(s, i, j)) { const validPalindrome = s.substring(i, j+1); if (longestPalindrome.length < validPalindrome.length) { longestPalindrome = validPalindrome; } } } } return longestPalindrome; }