What Is Longest Palindromic Substring?

What Is Longest Palindromic Substring?
What Is Longest Palindromic Substring?

Introduction

Finding substrings and subsequences are popular topics in programming job interviews, along with array, binary tree, and linked list data structures.

Today we will look at a problem called “Longest Palindromic Substring,” which is frequently asked in product companies such as Amazon, Microsoft, Adobe.

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

Example 1:
Input: s = “cacad”
Output: “cac”
Note: “aca” is also a valid answer.


Example 2:
Input: s = “ceed”
Output: “ee”

Note: A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Let us first define substring before continuing to the approaches.

What is a substring? 

As the name suggests, ‘sub + string’ is a subset of a string. By subset, we mean the contiguous part of a character array or string.

For example:

In the diagram above, CODING, NINJA, DING all are substrings of the string ‘CODINGNINJAS’.

Method 1: Brute Force 

The straightforward approach is to determine whether or not each substring is a palindrome. 

Approach

Execute three nested loops: the outer two loops pick all substrings one by one by fixing the corner characters, and the inner loop determines whether the picked substring is a palindrome or not.

The C++ code for the above approach is provided below to help you understand it better:

//C++ brute force solution for longest palindrome substring
#include <bits/stdc++.h>
using namespace std;

// Function to print a substring str[low..high]
void printSubStr(string str, int low, int high)
{
	for (int i = low; i <= high; ++i)
		cout << str[i];
}

// This function prints the
// longest palindrome substring
// It also returns the length
// of the longest palindrome
int LPS(string str)
{
	// get length of input string
	int n = str.size();

      // if string is empty return 0
      if (n==0)
      {
	    cout << "Input string is empty ";
        return 0;
      }

	// All substrings of length 1
	// are palindromes
	int maxLength = 1, start = 0;

	// Nested loop to mark start and end index
	for (int i = 0; i < str.length(); i++) {
		for (int j = i; j < str.length(); j++) {
			int flag = 1;

			// Check palindrome
			for (int k = 0; k < (j - i + 1) / 2; k++)
				if (str[i + k] != str[j - k])
					flag = 0;

			// Palindrome
			if (flag && (j - i + 1) > maxLength) {
				start = i;
				maxLength = j - i + 1;
			}
		}
	}

      cout << "Longest palindrome substring is: ";
	printSubStr(str, start, start + maxLength - 1);

	// return length of LPS
	return maxLength;
}

int main()
{
	string str = "abacabacabb";
	int len = LPS(str);
	cout << "\nLength is: "<< len;
	return 0;
}

Output:

Longest palindrome substring is: bacabacab
Length is: 9

Complexity Analysis:

  • Time complexity: O(n^3)
  • Reason: Three nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n^3).
  • Auxiliary complexity: O(1)
  • Reason: As no extra space is needed.

To improve the brute force solution, we first look at avoiding unnecessary re-computation while validating palindromes. Consider the word “cbabc.” If we already know that “bab” is a palindrome, it is obvious that “cbabc” must be a palindrome because the two end letters on the left and right are the same.

So now let’s proceed to see the more optimised solution.

Method 2: Dynamic programming

Dynamic Programming or DP is just an optimisation technique. It is a method for solving problems by breaking them down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

Here the approach is as follows:

  • Maintain a bottom-up boolean table[n][n].
  • If the substring(S[i:j]) of the input string is a palindrome, the value of table[i][j] is true; otherwise, it is false.
  • To calculate table[i][j], first check the value of table[i+1][j-1], and if the value is true and str[i] is equal to str[j], we make table[i][j] true.
  • Otherwise, the table[i][j] value is set to false.

We define table(i,j) as follows:

table(i,j)=  True    //if the substring Si…Sj  is a palindrome
                  False   //Otherwise
Therefore, table(i,j)=(table(i+1,j−1)and Si==Sj)

The C++ code for the above approach is provided below to help you understand it better:

// C++ dynamic programming
// solution for longest palindrome substring

#include <bits/stdc++.h>
using namespace std;

// Function to print a substring
// str[low..high]
void printSubStr(string str, int low, int high)
{
	for (int i = low; i <= high; ++i)
		cout << str[i];
}

// This function prints the
// longest palindrome substring
// It also returns the length of
// the longest palindrome
int LPS(string str)
{
	// get length of input string
	int n = str.size();

      // if string is empty return 0
      if(n==0)
      {
	  cout << "Input string is empty ";
        return 0;
      }


	// table[i][j] will be false if substring
	// str[i..j] is not palindrome.
	// Else table[i][j] will be true
	bool table[n][n];

	memset(table, 0, sizeof(table));

	// All substrings of length 1
	// are palindromes
	int maxLength = 1;

	for (int i = 0; i < n; ++i)
		table[i][i] = true;

	// check for substring of length 2.
	int start = 0;
	for (int i = 0; i < n - 1; ++i) {
		if (str[i] == str[i + 1]) {
			table[i][i + 1] = true;
			start = i;
			maxLength = 2;
		}
	}

	// Check for lengths greater than 2.
	// k is length of substring
	for (int k = 3; k <= n; ++k) {
		// Fix the starting index
		for (int i = 0; i < n - k + 1; ++i) {
			// Get the ending index of substring from
			// starting index i and length k
			int j = i + k - 1;

			// checking for substring from ith index to
			// jth index if str[i+1] to str[j-1] is a
			// palindrome
			if (table[i + 1][j - 1] && str[i] == str[j]) {
				table[i][j] = true;

				if (k > maxLength) {
					start = i;
					maxLength = k;
				}
			}
		}
	}
      cout << "Longest palindrome substring is: ";
	printSubStr(str, start, start + maxLength - 1);

	// return length of LPS
	return maxLength;
}

int main()
{
	string str = "abacabacabb";
	int len = LPS(str);
	cout << "\nLength is: "<< len;
	return 0;
}

Output:

Longest palindrome substring is: bacabacab
Length is: 9

Complexity Analysis:  

  • Time complexity: O(n^2).
    Reason: It’s going to take two nested traversals.
  • Space Complexity: O(n^2).
    Reason: A matrix of size n*n is needed to store the dp table.

Could you improve the above-mentioned space complexity further, and if so, how? Yes, we could solve it in O(n^2) time while using only constant space.

Let us now look at a more optimised approach in terms of space complexity.

Method 3: (Space Optimised Approach)

Approach: “Expand around Centre”

We know that a palindrome mirrors itself around its centre. As a result, a palindrome can be expanded from the centre.

So what if we fix a centre and expand in both directions for longer palindromes?

From the above visualisation, we can observe that:

The objective is to consider one by one every index as a centre and generate all even and odd length palindromes while keeping track of the longest palindrome seen so far.

For odd length palindromes:

  • Fix a centre and expand in both directions, i.e., fix i (index) as the centre and two indices as i1 = i+1 and i2 = i-1.
  • If i1 and i2 are equal, then decrease i2 and increase i1 to find the maximum length.

For even length palindromes:

  • Take two indices, i1 = i and i2 = i-1
  • Compare characters at i1 and i2 to get the maximum length until all pairs of compared characters are equal.

The C++ code for the above approach is provided below to help you understand it better:

// O(n^2) time and O(1) space program to
// find the longest palindromic substring
#include <bits/stdc++.h>
using namespace std;

// A utility function to print
// a substring str[low..high]
void printSubStr(char* str, int low, int high)
{
	for (int i = low; i <= high; ++i)
		cout << str[i];
}

// This function prints the
// longest palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
int LPS(char* str)
{     
      // if string is empty return 0
	if(str[0] == '\0')
	{
	    cout << "Input string is empty ";
        return 0;
	}


      // The result (length of LPS)
	int maxLength = 1;

	int start = 0;
	int len = strlen(str);

	int low, high;

	// One by one consider every
	// character as centre
	for (int i = 1; i < len; ++i) {
		// Find the longest even length palindrome
		// with center points as i-1 and i.
		low = i - 1;
		high = i;
		while (low >= 0 && high < len
			&& str[low] == str[high]) {
			--low;
			++high;
		}

		// Move back to the last possible valid palindromic substring
		// as that will anyway be the longest from above loop
		++low; --high;
		if (str[low] == str[high] && high - low + 1 > maxLength) {
			start = low;
			maxLength = high - low + 1;
		}

		// Find the longest odd length
		// palindrome with center point as i
		low = i - 1;
		high = i + 1;
		while (low >= 0 && high < len
			&& str[low] == str[high]) {
			--low;
			++high;
		}

		// Move back to the last possible valid palindromic substring
		// as that will anyway be the longest from above loop
		++low; --high;
		if (str[low] == str[high] && high - low + 1 > maxLength) {
			start = low;
			maxLength = high - low + 1;
		}
	}

	cout << "Longest palindrome substring is: ";
	printSubStr(str, start, start + maxLength - 1);

	return maxLength;
}



int main()
{
	char str[] = "abacabacabb";
	int len = LPS(str);
	cout << "\nLength is: "<< len;
	return 0;

}

Output:

Longest palindrome substring is: bacabacab
Length is: 9

Complexity Analysis:  

  • Time complexity: O(n^2).
    Reason: Since the expanding of a palindrome around its centre can take O(N) time and there would be at most (2 * ‘N’ – 1) centres, so the overall time complexity will be O(N ^ 2).
  • Space Complexity: O(1).
    Reason: No extra space is needed.

Now that you’re aware of all the approaches let’s submit Longest Palindromic Substring to CodeStudio and get it accepted right away.

Frequently Asked Questions

What is a palindrome string?

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

IS NULL string a palindrome?

Yes, some programmers consider a NULL string a palindrome while others do not.

Can a single character be a palindrome?

Yes, a single character is considered a palindrome because it reads the same forward and backwards.

How do I find the longest palindromic substring?

There is a total of four approaches to finding the longest palindromic substring as discussed above:

1. Brute Force
2. Dynamic Programming
3. Expand around centres
4. Manacher’s Algorithm

Which algorithm is used to find the longest palindrome?

Manacher’s Algorithm is an optimised algorithm to find the longest palindrome.

Key Takeaways

This article discussed the solution of the longest palindromic substring ranging from brute force to optimised. We took advantage of mirror indexing and learnt how to find palindromes by expanding around centres.

You might assume we can’t improve it any further, but there is an O(N) algorithm known as Manacher’s algorithm.

Manacher’s algorithm is faster because it reuses precomputed data when a palindrome exists inside another palindrome. Don’t worry; We will discuss Manacher’s algorithm in detail in our upcoming blog.

 It is rigorous practising which helps us to hone our skills. You can find a wide variety of practice problems, specifically dynamic programming to practically utilise the knowledge you gained here.

Apart from this, you can use CodeStudio to practise a wide range of DSA questions typically asked in interviews at big MNCs. This will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based organisations.

By Aanchal Tiwari

Exit mobile version