# Longest Palindromic Substring — Day 22(Python)

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:

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.

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

3. All the value along the diagonal will be True. Every letter is a palindrome, which is why we mark diagonals 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.

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.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt