Longest Palindromic Substring — Day 22(Python)

Image from Etymology

Today’s question is on Strings. Another favorite of FANG company interviewers for the coding round. Let us look into the question.

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

Before looking at the solution, let us understand palindrome. According to Wikipedia,

“A palindrome is a word, number, phrase, or other sequences of characters that reads the same backward as forward, such as madam, racecar.”

How should we use this information to solve the given problem?

One way to solve is by creating all possible substrings, eliminate non-palindromic substring, and find the maximum length among the remaining substring.
To check if a string is palindrome or not, compare the word with its reverse. If both are the same, then the word is palindromic.

Check the following code snippet that implements the above logic.

class LongestPalindromeFinder:
    def longestPalindrome(self, s: str) -> str:
        max_len = 0
        max_word = ""
        for first in range(len(s)):
            for second in range(first+1, len(s)+1):
                word = s[first:second]
                if (word == word[::-1]):
                    if max_len < len(word):
                        max_len = len(word)
                        max_word = word
        return max_word

Complexity analysis

Time Complexity

We have two for loops that traverse through the String and slices at each point which takes O(N²). Apart from the loops, we are also reversing the sliced word, which takes O(N). Hence the time complexity is O(N³), where N is the length of String.

Space Complexity

We are not using any extra space while implementing the algorithm, and hence the space complexity is O(1).

If we run the above code in leetcode, we will hit Time Limit Exceed error. How should we improve the time complexity?

I learned how to solve this problem using the algorithm from geeksforgeeks. I will try my best to explain the algorithm.

1. Start by creating a 2D matrix of size the same as the length of the original string. Initialize the matrix as False.

Initial Matrix

2. The rows represent the start index of the substring, and columns represent the end of the substring.

For eg: S = “abadabs”

matrix[2][4] = “ada”

3. All the value along the diagonal will be True. Every letter is a palindrome, which is why we mark diagonals as True.

Diagonals marked as True

4. We will start from the bottom -right cell of the matrix. Since we visited this cell earlier, we will move above row. Check if the character in the current row is equal to the character in the current column. If no, move to the character in the next column. If yes, check the truth value at the cell diagonally-left of the current cell, this will be the value for the current cell. We do this because for a string to be a palindrome, not just characters at the end have to be the same, but the inner characters need to be the same.

Marking other cells

While performing the above operations, whenever a new cell is marked True, check for the length of the substring, and store if the length is higher than the earlier stored substring.

class LongestPalindromeFinder:
    def longestPalindrome(self, s: str) -> str:
        len_palindrome = 0
        palindrome = ""
        len_s = len(s)
        if(len_s < 2):
            return s
        p_table = [[False for row in range(len_s)] for col in range(len_s)]
        for i in range(len_s):
            p_table[i][i] = True
            if(len(s[i:i+1]) > len_palindrome):
                len_palindrome = len(s[i:i+1])
                palindrome = s[i:i+1]
        for i in range(len_s -2,-1, -1):
            for j in range(i+1, len_s):
                if(s[i] == s[j]):
                    if((j - i == 1) or (p_table[i+1][j-1])):
                        p_table[i][j] = True
                        if len_palindrome < j - i + 1:
                            len_palindrome = j - i + 1
                            palindrome = s[i: j+ 1]
        
        return palindrome

Complexity analysis

Time Complexity

We have two for loops that traverse through the matrix that takes O(N²).

Space Complexity

We are using a matrix of size N² while implementing the algorithm, and hence the space complexity is O(N²).

We do have Manacher’s algorithm that solves the Longest Palindromic substring in Linear Time, but it is for another day.

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.