Microsoft Interview Question: Given a string, find out the ... | Glassdoor

Interview Question

Software Development Engineer Software Development Engineer Interview Seattle, WA

Given a string, find out the longest palindrome substring.


Interview Answer

1 Answer


The naïve solution is to try all O(n^2) substrings, each one in O(n) time, for an O(n^3) solution.

We can improve if we try each of the O(n) possible locations for the middle character and scan in both directions as long as the characters on both sides continue to match. This is O(n) for each of O(n) possible middle locations, and thus up to O(n^2) overall. For processing natural language, this might be a very good algorithm, because the runtime is O(n+s), where s is the total number of palindromes (s is up to O(n^2) in theory, hence the O(n^2) worst-case bound, but is likely to be much much smaller for a natural language text).

To go beyond O(n^2) takes some tougher concepts. You can verify whether a palindrome of any given length X exists by using Rabin-Karp text matching in O(n) expected time. If you want the largest palindrome, you could binary search for the correct value of X. This works because if there is a palindrome of length a, there is also one of length b for b < a, at least for palindromes that are both even length or both odd length (you can run the algorithm twice, once for even-length and once for odd-length palindromes). So you start out looking for a palindrome of size N/2 -- if found, try looking for 3N/4, if not found, look for N/4.This technique is enough to produce a solution having O(nlogn) expected time.

The problem can be solved in O(n) using a suffix tree.

Finally, there are ways to produce a KMP-like algorithm to solve this problem in O(n) with no fancy data structures.

Anonymous on Nov 4, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.