Algorithms {Longest Palindromic Substring}

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 🙂

For example we have string aba, we can use something like level order traversing and, yes, it would be BFS is not it ??? Execution steps like that :

  •  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 🙂

I’ve tried and it’s working 🙂

Good and thanks !!!

Leave a Reply

Your email address will not be published. Required fields are marked *