4
\$\begingroup\$

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
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.