Longest Palindrome Substring in Python

Concepts involved: Strings, Slicing, Substring and Reversing

A palindrome is a word or string that reads the same from left to right and from right to left.

For example: MOM = MOM, DAD=DAD

A substring is a continuous sequence of characters taken from a string.

For example, if the string is "hello":

• "hel" is a substring.
• "ell" is a substring.
• "llo" is a substring.
• "hlo" is not a substring because the characters are not continuous.

Leetcode question : Return the longest palindrome substring in a given string.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Flow diagram: s = “babad”

Visual Representation

Python Code:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1: 
            return s 
         
        Max_Len=1 
        Max_Str=s[0] 
        for i in range(len(s)-1): 
            for j in range(i+1,len(s)): 
                if j-i+1 > Max_Len and s[i:j+1] == s[i:j+1][::-1]: 
                    Max_Len = j-i+1 
                    Max_Str = s[i:j+1] 
 
        return Max_Str
        

Lets Break it Down!!

First part

if len(s) <= 1:    return s

If the string is:

"a"

or:

""

then it is already a palindrome. So just return it.

We start with assigning variables:

Max_Len = 1
Max_Str = s[0] which means Max_Str =  "b"   

Current best: we are trying to keep track of the best palindrome 
we've found so far.
┌───────────────┐
│ "b"           │
│ length = 1    │
└───────────────┘

Now comes the FOR loops:

First forloop: here i chooses where the substring starts.

for i in range(len(s)-1):

index :  0   1   2   3   4
         b   a   b   a   d

Now i goes through:

0
1
2
3

Second for loop: here j chooses where the substring ends.

for j in range(i+1, len(s)):

i ───────── j
↓           ↓
b   a   b   a   d

Let’s see what happens when i = 0

Now j goes through:

1
2
3
4

So we get:

j = 1

s[i:j+1]

becomes:

s[0:2]

which gives: "ba"

j = 2

s[0:3]

gives: "bab"

j = 3

s[0:4]

gives: "baba"

j = 4

s[0:5]

gives: "babad"

So the nested loops are basically generating:

i = 0

"ba"
"bab"
"baba"
"babad"

Then i changes.

Get Ruby’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

What does this line do?

s[i:j+1] == s[i:j+1][::-1]

Let’s take:

"bab"

First:

s[i:j+1]

gives:

"bab"

Then:

s[i:j+1][::-1]

reverses it:

"bab"

So:

"bab" == "bab"

is:

True

Therefore:

"bab" is a palindrome.

Let’s try "baba"

"baba"

Reverse it: "abab"

Compare: "baba" == "abab"

That’s:

False

So "baba" is not a palindrome.

This part is clever

if j-i+1 > Max_Len

What is: j - i + 1 It’s simply the length of the substring.

For example:

i = 0
j = 2

Then:

j - i + 1
= 2 - 0 + 1
= 3

And: s[0:3] = "bab" which has length 3.

So:

j-i+1 > Max_Len

means:

“Is this substring longer than the longest palindrome I’ve found so far?”

Why do we need this condition?

Suppose we’ve already found:

Max_Str = "bab"
Max_Len = 3

Then we find:

"aba"

It’s also a palindrome.

But:

len("aba") = 3

and:

3 > 3

is:

False

So we don’t replace "bab".

That’s perfectly fine because both are longest palindromes.

If we find something longer

Suppose:

Max_Str = "bab"
Max_Len = 3

Then we find:

"abba"

Length:

4

Now:

4 > 3

is true.

So:

Max_Len = j-i+1 
Max_Str = s[i:j+1]

becomes:

Max_Len = 4
Max_Str = "abba"

So this approach is basically:

Brute Force with String Slicing which has a Time complexity of O(n²)