How to Solve Longest Palindromic Substring
Longest Palindromic Substring Introduction
Longest Palindromic Substring Introduction
The Longest Palindromic Substring problem asks us to return the longest palindromic substring in a given string s. This problem has an intuitive solution of expanding around the center but can often catch interviewees off-guard when faced with even-length palindromes.
Longest Palindromic Substring Problem
Longest Palindromic Substring Problem
Given a string s, return the longest palindromic substring in s.
Example Inputs and Outputs
Example 1
Input: s = "babad"
Output: "bab"
Example 2
Input: s = "cbbd"
Output: "bb"
Longest Palindromic Substring Solutions
Longest Palindromic Substring Solutions
To find the longest palindromic substring in a given string, we can use a simple approach called "expand around center". Imagine you're reading the string from left to right, character by character. At each character, you can think of it as a potential center of a palindrome. To check if there's a palindrome centered around that character, you expand outward from the center and compare characters on both sides. If the characters match, you continue expanding until you find a mismatch or reach the boundaries of the string. By doing this for each character in the string, you can find the longest palindrome.
The tricky part is handling palindromes with even lengths. In that case, the center of the palindrome is between two characters rather than a single character. So, we treat each character and the space between two characters as potential centers and expand around them. By trying different centers and expanding around them, we can find the longest palindromic substring in the given string.
def longestPalindrome(s):
n = len(s)
# Edge case of string length 0 or 1
if n <= 1:
return s
start = 0
maxLength = 1
# Helper function to expand around center
def expandAroundCenter(left, right):
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
# Iterate through each character in the string
for i in range(n):
len1 = expandAroundCenter(i, i)
len2 = expandAroundCenter(i, i + 1)
currLen = max(len1, len2)
# Update longest
if currLen > maxLength:
maxLength = currLen
start = i - (currLen - 1) // 2
# Return result
return s[start:start + maxLength]
# Test case
input_string = "babad"
result = longestPalindrome(input_string)
print(result)1def longestPalindrome(s):
2 n = len(s)
3
4 # Edge case of string length 0 or 1
5 if n <= 1:
6 return s
7
8 start = 0
9 maxLength = 1
10
11 # Helper function to expand around center
12 def expandAroundCenter(left, right):
13 while left >= 0 and right < n and s[left] == s[right]:
14 left -= 1
15 right += 1
16 return right - left - 1
17
18 # Iterate through each character in the string
19 for i in range(n):
20 len1 = expandAroundCenter(i, i)
21 len2 = expandAroundCenter(i, i + 1)
22 currLen = max(len1, len2)
23
24 # Update longest
25 if currLen > maxLength:
26 maxLength = currLen
27 start = i - (currLen - 1) // 2
28
29 # Return result
30 return s[start:start + maxLength]
31
32# Test case
33input_string = "babad"
34result = longestPalindrome(input_string)
35print(result)Time/Space Complexity Analysis
- Time Complexity: O(n²), as we have nested loops iterating through the string. The outer loop runs for each character in the string, and the inner loop expands around the center to find palindromes. In the worst case, we may need to expand on both sides for every character, resulting in a quadratic time complexity.
- Space Complexity: O(1), as we only use a constant amount of extra space to store variables and temporary values.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
