Longest Palindromic Substring

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.

Longest Palindromic Substring

To find even length palindrome we fix center between two nearby letters in S and also expand it in both directions.

Longest Palindromic Substring

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 :)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s