Leetcode, longest palindromic substring

Question

Here's a link

Given a string s, return the longest palindromic substring in s. A string is called a palindrome string if the reverse of that string is the same as the original string.

Example 1:

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

Example 2:

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

---

from collections import defaultdict def is_palindrome(s): return s == s[::-1] def solve(s): seen = defaultdict(list) found = '' for i, char in enumerate(s): if seen[char]: for j in seen[char]: ss = s[j : i + 1] if is_palindrome(ss): found = max(ss, found, key=len) break seen[char].append(i) if not found: found = s[0] return found 

Answer 1

Well done optimization over a brute-force O(N^2) solution. It is still O(N^2) of course but will run much faster, especially for short strings of random characters. If you're interested in a linear solution, here it is (although it's not something you can realistically invent in 5 minutes).

Some interviewers might complain about naming: found sounds like a boolean name for whether or not a palindrome was found, s and ss don't say anything at all. It may take some time to come up with a fitting name, but if you inform the interviewer why you're taking your time, it will be a big plus: naming is very important in production code.

Also, you didn't specify the constraints so this solution breaks if the string is empty. Make sure to check all the corner cases and constraints during a real interview, it is very important. Being able to find those corner cases is one of the main things such interviews are meant to check.