Today we will talk about “Longest Palindromic Substring” problem. I’ve developed solution about year ago but a few days remembered it and thought about it.
So, full problem description:
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Ok, good, on the face of it, we can use some simple naive algorithm with O^2 complexity and problem will be solved. Good … But how we can check borders of the longest palindromic substring ? Oh, that is very interesting 🙂
- index on a; try to left – null, try to right – not null; result is not palindrome; increase index;
- index on b; try to left – a, try to right a, good, next level, left and right – nulls , good, palindrome; store to max palindromic instance; increment index;
- and so on ..
OK, it’s working on simple string. What about bb string ? …
Hm, if we start from b we can get just b as max substring but we should return bb … Interesting…
Naturally we can/should check index i and i+1 and compare result, is not it ? I think so, OK, try to write and submit code to leetcode 🙂
[crayon-5bf06d29e4349596815933/] I’ve tried and it’s working 🙂
Good and thanks !!!