Leetcode – 5. Longest Palindromic Substring
Problem
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"
Solution
For me, this problem is literally hard. It’s easy to solve it using brute force method but I don’t know the better method.
Brute force
The brute force method is straight forward.
– Loop through the string, add the character to a substr.
– Continue with another loop to build the substr based on the first character.
– Check if it’s palindromic or not
def longestPalindromeBruteForce(self, s: str) -> str:
max_length = 0
result = ""
for i in range(len(s)):
substr = s[i:]
for j in range(len(substr)):
temp = substr if j == 0 else substr[:-j]
if temp == temp[::-1]:
if max_length < len(temp):
max_length = len(temp)
result = temp
break
return resultResult is bad, but at least it works.
Optimized solution
Because I have no clue how to solve this problem, I used Gemini Guided Learning mode to teach me how to solve it. Make sure that you tell it to not generate any code. In my opinion, the Guided Learning mode is really good.
The idea is get a character in the string then expanding around that character. To check if it’s a palindrome or not, we just need to compare the left and right character. No need to rebuild the substring then use string flip to check.
def longestPalindrome(self, s: str) -> str:
n = len(s)
if s == "":
return ""
start = 0
end = 0
for i in range(n):
len1 = self.expandAroundCenter(s, i, i)
len2 = self.expandAroundCenter(s, i, i + 1)
max_len = max(len1, len2)
if max_len > (end - start):
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
def expandAroundCenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1Final result:
