Today, we will discover one of the basics algorithms to find the longest palindromic substring.
Problem:
Given a string S, find the longest palindromic substring in S.
Difficulty: Easy
Practice: Leetcode
Examples:
1. S = "abad", Result = "aba" 2. S = "codeedoc", Result = "codeedoc"
Solution:
To come up with a solution we need to understand what the palindrome is. Basically, this is just a word which reads the same backward as forward (for more details see).
The main idea is to find all palindromes in S with even and odd lengths and keep track which one is the longest. To find odd length palindromes we fix center for every letter in S and expand it in both directions.
To find even length palindrome we fix center between two nearby letters in S and also expand it in both directions.
While expanding, if two opposite letters are equal then we add them to our potential palindrome.
Time complexity: O(N^2)
Space complexity: O(1)
That’s all for today. You can find the source code here, but I suggest you implement it by yourself.
Thank you for reading my blog and see you in a leaderboard :)