Longest Palindromic Substring

Problem Statement

Given a string s, we have to return the longest palindromic substring.

Note: Palindromes are words or phrases that read the same backward and forward, letter for letter, number for number, or word for word. Source: Grammarly

Examples

Input: s = “babad”

Output: “bab”

Input: s = “dfgggggkl”

Output: “ggggg”

Input s = “a”

Output: “a”

Thought Process

In any given string, to find the longest palindromic substring, the brute force approach would be to consider every possible substring and then have a helper function to check if it is a palindrome. This results in a cubic complexity for a string of length N. Why O(N³) complexity? To check if a string is a palindrome or not, we will have to traverse through the whole substring. At the worst case, this will be the entire string s. This takes O(N). We will then have to use two for loops to check each possible substring which will be O(N²). Now let’s think of an efficient way of doing this.

There are two types of palindromes.

• Palindromes with an even number of letters. Examples: “aa”, “abba”, “cdeedc”
• Palindromes with an odd number of letters. Examples: “a”, “aba”, “cdedc”

The speciality of palindromes is that they expand from a central point and mirror each other on the left and right. How to define what is the center? In an even length palindrome, the center is in between two letters. In “abba”, the center is in between the two “b”s. In “aba”, which is an odd length palindrome, the center is “b”.

How many possible centers are there in a given palindrome?

Example 1: “aba”

The possible centers to consider are a, a <-> b, b, b <-> a, a ie., 5 centers

Example 2: “abba”

The possible centers are a, a <-> b, b, b <-> b, b, b <-> a, a ie., 7 centers

For N = 2, possible centers = 3

For N = 3, possible centers = 5

For N = 4, possible centers = 7

For N = 5, possible centers = 9

Let’s look at the possible centers and see by how much does it go up for each value of N.

(5 – 3) = (7 – 5) = (9 – 7) = 2

We can calculate the number sequence by using xn. In this case x = 2, so 2N. We notice that for N = 3, the possible centers are not 2N = 6, we have to subtract 1. So the generalized sequence will be 2N – 1.

To solve the given problem, we can iterate through each character in the string while considering it as a possible center for a palindrome. We can then expand around this center while checking its left and right side for mirroring. Since there can be odd length and even length palindromes, we have to consider the max length between them.

To get the max odd palindrome, we pass the left and right pointers as the current character since the center is a single character. Example: “aba”, when i = 1 (b), the left and right starting points to expand around will both be “b”, i = 1.

To get the max even palindrome, we pass the left and right pointers as the current and next character since the center is in between two characters. Example: “abba”, when i = 1 (b), the left and right starting points to expand around will be “b”, i = 1 and the next “b”, i = 2.

We can then take the string with the max length between these two values.

longest_palindromic_substring = ""

for i in range(len(s)):
    odd_max = check_palindrome(s, i, i)
    even_max = check_palindrome(s, i, i+1)

    longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len)

Now let’s write a helper function to check if the given string is a palindrome.

def check_palindrome(s, left, right):

    while left >= 0 and right < len(s):

        if s[left] == s[right]: # check mirroring
            left -= 1
            right += 1
        else:  # Break the loop if the characters mismatch
            break  

    return s[left+1: right]

Complexity

O(N²) time – O(N) to expand around each center and O(N) to check if the substring is a palindrome

O(1) space

Putting it all together.

Solution

def find_longest_palindromic_substring:
    
    if not s:
        return s
    
    def check_palindrome(s, left, right):

        while left >= 0 and right < len(s):

            if s[left] == s[right]: # check mirroring
                left -= 1
                right += 1
            else:  # Break the loop if the characters mismatch
                break  

        return s[left+1: right]

    longest_palindromic_substring = ""

    for i in range(len(s)):
        odd_max = check_palindrome(s, i, i)
        even_max = check_palindrome(s, i, i+1)

       longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len) # This will return the max value based on string length (key = len)

    return longest_palindromic_substring
    

Hope you enjoyed this step by step problem solving approach for the longest palindromic substring problem and learnt a thing or two about palindromes!