Longest Palindromic Substring

Problem Statement

The Longest Palindrome in a String in one of the most classic problems in DSA. The problem statement goes like this:

Given a string, find the maximum length substring of it that is a palindrome.

Input: String

Output: String

Before we move on to examples and the solution to this problem, make a note of the definition of 'substring' and 'palindrome'. A word - 'scaler' can have the following substrings - 'sca', 'ler', 'aler' since all these characters are present in continuity in our string. However, the strings - 'sclr' or 'cer' are not substrings since the characters do not have a continuous presence in the string. A palindrome is a set of characters that is the same when read from left to right as well as from right to left. For example - '12321' or 'malayalam' etc.

Examples

1. string = findnitianhere Longest Palindrome in the String = indni Length of the longest palindrome = 5

2. string = abcbedrardea Longest Palindrome in the String = edrarde Length of the longest palindrome = 7

Examples Explanation

1. In the first string, the only palindrome present is the substring 'indni' and the length of this palindrome is 5.
2. In this string, there are two palindromes - 'bcb' and 'edrarde' and the longest palindromic substring is 'edrarde'. And the length of this substring is 7.

Constraints

1. The length of the string ranges between 1 and 1000 both inclusive 1 <= length(string) <= 1000
2. The string contains only digits and English alphabets.

Approach 1 - Brute Force / Naive Approach

The first approach that comes to mind is the naive or brute force approach. Naturally, in this method, you would traverse the string, and find every substring and check if it is a palindrome.

To do this, we would require 3 for loops. The first two loops would find every substring of the given string, and the third loop would check if the substring is a palindrome or not. At the same time, we would keep check of the length of the substring, if it is a palindrome, so as to return the longest palindromic substring.

A point that is worthy of noting here, is that every substring of length '1' is a palindrome.

So what we're going to do is, initially, keep a variable that stores the current maximum length of the palindrome that we have seen, and another variable that just stores the length of our input string. Now, to check if a string is a palindrome, one helpful way is to reverse it and compare it with the original string, or substring in this case.

Here's how this algorithm looks:

Code Implementation

C++:

Output:

Java:

Output:

Python:

Output:

Time Complexity

Time Complexity: O(n³), where n is the length of the string. The reason for such a high time complexity is the three nested loops in the code.

Space Complexity

Space Complexity: O(1) We are not making the use of any extra space.

Approach 2 - Dynamic Programming

To understand the concept of dynamic programming in detail, and solve basic problems, refer to this article on 1 dimensional dynamic programming and this article for this problem. Moving on to our problem, it can be solved using a more optimized version of the previous approach which is dynamic programming. To re-iterate, dynamic programming solves problems by breaking down the big problem into smaller sub problems, and using the results of the computations performed on the subproblems. The results of the smaller subproblems are stored and utilized.

In this case, how would we do it? Let's say the longest palindrome in our string is abcdedcba. If we already know that 'ded' is a palindrome, it is sure that 'cdedc' is also a palindrome since the first and last alphabets of the new string are the same. And similarly, if we know that 'cdedc' is a palindrome, it is not tough to find out that 'bcdedcb' and 'abcdedcba' are also palindromes. Do you see how this is going?

Keeping this in mind, we're going to have a function P(i, j) such that: Which can also be written as:

-- which is nothing but the condition discussed above - 'ded' is a palindrome, and so is 'cdedc' since the first and last characters are same.

Hence, the base cases are:

Using the above observations, we can yield a very straightfoward dynamic programming solution. In this approach we will first initialize the one letter, and two letter palindromes (both letters are same - 'aa' or 'ee') and then grow by finding all the 3 letter palindromes and so on.

The traditional approach of a dynamic programming solution is to create a table. In this table, every row and column represents the slicing indices on the string, both inclusive. For example, if we have a string 'babad' then the value of dp[2][3] will represent s[2:3] (similar to python syntax) i.e. ba.

Steps to solving the problem:

• Create a boolean table (dp) of size n * n (n is length of input string) that will be filled in the bottom-up manner.
• If the value at dp[i][j] is True, then the sliced substring s[i] is a palindrome. If the value at dp[i][j] is False, then the sliced substring s[i] is not a palindrome.
• Now, to fill in the values in the table, we will make use of the base case note that we made. The value at dp[i][j] will be filled according to dp[i + 1][j - 1] and the characters in the string at s[i] and s[j]. If dp[i + 1][j - 1] is True, and if s[i] == s[j], then dp[i][j] will also be true, else False.
• Initially we would be filling up the palindromes of length 1 and 2, i.e. single characters and repeating characters.

Since the string 'scaler' has no palindromes, this is what the table would like.

Let's now try implementing this approach in code and discuss the time and space complexities.

Code Implementation

C++

Output:

Java:

Output:

Python:

Output:

Time Complexity

Time complexity of this approach: O(n²) where n is the length of the string. The time complexity of this approach is better than the naive or brute force solution, but is still not the most optimal solution since we require 2 nested traverals of the string.

Space Complexity

Space complexity of this approach: O(n²) where n is the length of the string. In the dynamic programming approach we store the results of the sub problems in a table of size n * n and hence the space complexity of this approach is O(n²).

Approach 3 (Optimal Approach) - Expand around Centre

To understand the optimal approach, we must first make an important observation, that is, every palindrome mirrors around its centre. For example, for the palindrome - 'abccba': This means that a palindrome can be expanded around its centre.

In the complete string, there are only 2n - 1 such centres available for expansion, where n is the length of the string. Why? This is because the centre around which the palindrome is mirrored, can be between two letters, and can also be a particular letter. The case of the mirror being a character in the string, is for odd length palindromes as - 'aba' and the case of the mirror being between characters is for even length palindromes as given in the images above.

So what is the approach to solve this problem? We're going to consider every index of the string as the middle point or the centre of a possible palindrome and expand around it. We will expand till we find same characters.

Algorithm

Here's the algorithm to solve the problem:

• Traverse the string and consider every index as the centre around which the palindrome is mirrored. We will encounter two cases (in both the cases, i is the loop variabe):
  • Case 1: The length of the palindromic substring is even:
    • If the palindrome is of even length, we will assign 2 pointers namely left and right pointers and initialize them with values i - 1 and i which is centre and then expand left and right in both directions, till the condition s[left] == s[right] is satisfied.
  • Case 2: The length of the palindromic substring is odd:
    • If the palindromic substring is of odd length, the centre is likely to be a particular character. In which case, we will assign the same left and right pointers and initialize them with values i - 1 and i + 1 with i as the centre. Post that, we will again expand around the centre till the condition s[left] == s[right] is satisfied.
• While this is done, we will maintain the length of the longest palindromic substring encountered and the substring, and return it.

Code Implementation

C++:

Output:

Java:

Output:

indni

Python:

Output:

Time Complexity

The time complexity of this approach is: O(n²) Expansion around a particular palindrome, in the worst case would take O(n) time and hence, the overall time complexity of this approach would be O(n²).

Space Complexity

Space complexity of this approach: O(1) In this approach we are not making the use of any extra space and hence, the space complexity is linear.

Approach 4 - Manachar Algorithm

For a detailed solution, to this problem using the manacher's algorithm, it is strongly recommended that you refer to this post by scaler topics. Manachar's algorithm can be used to solve the current problem at hand with a linear time complexity.

Manacher's algorithm is essentially designed to find the palindromic substrings that have odd lengths only. To use it for even lengths as well, we can tweak the input string by inserting a character such as - "#" at the beginning and each alternate position after that (for example, changing a string "abcaac" to "#a#b#c#a#a#c#").

Algorithm

Here's the algorithm that solves the problem at hand:

• Create an array or a list (sChars) of length strLen which is 2∗n+3 (n being the length of the given string), to modify the given string.
• Assign the first and last element of sChars to be "@" and "$", respectively.
• Fill the blank spaces in sChars by characters of the given string and "#" alternatively.
• Declare the following variables
  • maxLen = 0, which is the variable that stores the current maximum detected length of the palindromic substring
  • start = 0, the variable that indicates the position from where we will start the search for the longest palindromic substring
  • maxRight = 0, that indicates the highest position of the rightmost character, of every palindrome detected.
  • center = 0, which is nothing but the center of the palindrome detected.
• We would next create a list / array, p that records the width of each palindrome about their center, where the center is the corresponding character in our array sChars.
• Next, we will start a for loop that iterates from 1 to the length of the string, with the loop variable i that increments with every iteration.
• In every iteration, we will check the condition i < maxRight. If it is true, then we will assign the minimum of maxRight - i and p[2 * center - i] to p[i].
• We will next create a nested while loop inside the for loop, to count with width along the center, condition being, sChars[i + p[i] + 1] is equal to sChars[i - p[i] - 1], if yes, increment p[i] by 1.
• To update the center, we need to check if i + p[i] is greater than maxRight, if yes, then we will assign center to be 1, and maxRight to be i + p[i].
• To update the maximum length of the palindromic substring detected, we check if p[i] is greater than maxLen, if yes, then change the value of start to be (i - p[i] - 1) / 2, and maxLen to be p[i].
• Exit the for loop, and return the longest palindromic substring in the given string, starting from start and ending at start + maxLen - 1.

Code Implementation

C++:

Java:

Python:

Output:

Time Complexity

Time complexity of this approach: O(n) The time complexity of this approach the first time might look like it is O(n²), however, the inner while loop will get executed at most n times, still leaving the time complexity to be linear.

Space Complexity

Space complexity of this approach: O(n) We create an array in this approach of size n and hence, the space complexity is linear as well.