Last Updated on April 26, 2023 by Prepbytes
A palindrome is a sequence of characters that reads the same forwards and backward. Finding the longest palindromic substring is a common problem in computer science and has applications in many fields such as genetics, bioinformatics, and data compression. In this article, we will discuss different approaches to finding the longest palindromic substring.
How to Find the Longest Palindrome Substring?
The problem is to find the longest palindromic substring in a given string. A palindromic substring is a substring that reads the same forwards and backward. The length of the substring can be odd or even.
Example:
-
Input: "babad"
Output: "bab" -
Input: "cbbd"
Output: "bb” -
Input: "racecar"
Output: "racecar"
Approaches to Solve Longest Palindromic Substring
Below are some approaches to solving the Longest Palindromic Substring problem.
Approach 1: Brute-Force Approach
In this approach, we generate all possible substrings of the given string and check if each substring is a palindrome. We keep track of the longest palindromic substring found so far. Let’s understand this approach step by step.
- Step 1. We can find every possible substring of the given string and then find the largest string that is palindromic in them. We print such string.
- Step 2. This approach takes two loops for finding all substrings, and a loop for checking if the substring is palindrome or not for every possible substring found. Hence time complexity for this approach is O(N^3).
- Step 3. If the length of the string goes from 1 to 10^3, this approach is inefficient for such a string.
Approach 2: Efficient Approach
This approach is better than the brute force approach and the steps involved in this approach are as follows:
- Step 1. The first step of the algorithm is to consider both odd and even-length substrings and find the longest palindromic substring for each. This is done by iterating through the string and checking for palindromic substrings of odd and even length. The longest palindromic substring out of the two is then printed as the final result.
- Step 2. For odd-sized substrings, we start from a single pointer at the current index and expand both ways by comparing the characters on each side. If both characters are equal, the pointer expands further. The process continues until the characters on both sides are not equal or the string ends. At each step, we check the length of the current substring and compare it with the longest palindromic substring found so far. If the current substring is longer, we update the length of the longest palindromic substring and save its start and end index.
- Step 3. For even-sized substrings, we initialize with two pointers i.e. left and right, and expand them on both sides by comparing the characters. The process is the same as that for odd-sized substrings.
- Step 4. Finally, we perform the above iteration for every index of the substring. This means that we check for palindromic substrings of all possible lengths starting from each character in the string. The longest palindromic substring found in this process is the final result.
Example
- Let’s assume string S is bbbbbabbb. So we iterate over string character by character and check for both odd sized and even sized palindromes having current character as middle element.
Odd-sized Palindromes : We use a pointer start, we’ll iterate towards both end of start and will continue until characters on both sides does’nt match
For i=1 :
From above image, we can see that palindromic substring found is ‘bbb’ with length 3.
For i=2 :
From above image, we can see that palindromic substring found is ‘bbbbb’ with length 5.
For i=3 :
From above image, we can see that palindromic substring found is ‘bbb’ with length 3.
For i=4 :
From above image, we can see that palindromic substring found is ‘b’ with length 1.
For i=5 :
From above image, we can see that palindromic substring found is ‘bbbabbb’ with length 7.
For i=6 :
From above image, we can see that palindromic substring found is ‘b’ with length 1.
For i=7 :
From above image, we can see that palindromic substring found is ‘bbb’ with length 3.
Here we can see we find largest palindromic substring with length 7 at starting at index 2 and ending at index 8 having middle element at index i=5.
Even sized Palindromes : We use two pointers i.e. i and j for it, we’ll iterate towards both ends of i and j, we will continue until characters on both sides does’nt match
From above image, we can see that palindromic substring found is ‘bbbb’ with length 4.
From above image, we can see that palindromic substring found is ‘bbbb’ with length 4.
From above image, we can see that palindromic substring found is ‘bb’ with length 2.
From above image, we can see that no palindromic substring is found.
From above image, we can see that no palindromic substring is found.
From above image, we can see that palindromic substring found is ‘bb’ with length 2.
From above image, we can see that palindromic substring found is ‘bb’ with length 2.
Here we can see we find largest palindromic substring with length 4 which is smaller than the largest palindromic string found in odd section. So substring found in odd section is our final answer.
So our longest palindromic substring starts at index 2 and ends at 8 with size 7 and substring is ‘bbbabbb’
Code Implementation
#include <stdio.h>
int main()
{
int test;
scanf("%d",&test);
while(test--){
char a[1001];
scanf("%s",a);
int longestSubstring = 1, start=0, end = 0;
//Odd palindromic substrings
for(int i=1; i<strlen(a); i++){
int j= i-1, k=i;
while( j>=0 && k<strlen(a) && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
//Even palindromic substring
for(int i=0; i<strlen(a); i++){
int j= i-1, k=i+1;
while( j>=0 && k<strlen(a) && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
for(int i=start; i<=end; i++ )
printf("%c",a[i]);
printf("\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int test;
cin>>test;
while(test--){
string a;
cin>>a;
int longestSubstring = 1, start=0, end = 0;
//Odd palindromic substrings
for(int i=1; i<a.length(); i++){
int j= i-1, k=i;
while( j>=0 && k<a.length() && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
//Even palindromic substrings
for(int i=0; i<a.length(); i++){
int j= i-1, k=i+1;
while( j>=0 && k<a.length() && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
for(int i=start; i<=end; i++ )
cout<<a[i];
cout<<endl;
}
return 0;
}
import java.util.*;
import java.io.*;
import java.lang.Math;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc= new Scanner(System.in);
int test = sc.nextInt();
while(test != 0){
String a = sc.next();
int longestSubstring = 1, start=0, end = 0;
//Odd palindromic substrings
for(int i=1; i<a.length(); i++){
int j= i-1, k=i;
while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
//Even palindromic substrings
for(int i=0; i<a.length(); i++){
int j= i-1, k=i+1;
while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}
for(int i=start; i<=end; i++ )
System.out.print(a.charAt(i));
System.out.println();
test--;
}
}
}
Time Complexity Analysis:
The time complexity of this code is O(n^2), where n is the length of the input string. This is because the two nested loops iterate through the entire string for each test case, and the worst-case scenario is that the entire string is a palindrome.
Space Complexity Analysis:
The space complexity of the code is O(1) as only a few variables are used to store the indices and the length of the longest palindromic substring.
Conclusion
In conclusion, finding the longest palindromic substring can be achieved using various approaches. The brute force approach is not recommended for long strings due to its time complexity of O(n^3). The approach using loops is efficient with a time complexity of O(n^2) and a space complexity of O(1). It is important to choose the appropriate approach based on the size of the input string to ensure efficient and optimal execution.
FAQs
Here are some frequently asked questions on the topic of finding the longest palindromic substring.
Q1: What is the brute force approach to finding the longest palindromic substring?
Ans: The brute force approach is to generate all possible substrings of a given string and check if each substring is palindromic. This approach has a time complexity of O(n^3).
Q2: What is the loop approach to finding the longest palindromic substring?
Ans: The loop approach involves looping through each character in the string and expanding the palindrome on both sides to find the longest palindromic substring centered at that character. This approach has a time complexity of O(n^2) and a space complexity of O(1).
Q3: What is the time complexity of the brute force approach?
Ans: The time complexity of the brute force approach is O(n^3).
Q4: Why is the brute force approach not recommended for long strings?
Ans: The brute force approach is not recommended for long strings because it has a high time complexity of O(n^3), which can result in a significant increase in execution time.
Q5: What is the space complexity of the loop approach?
Ans: The space complexity of the loop approach is O(1) because it only uses a few variables to store the indices and the length of the longest palindromic substring.