Introduction:
We are given a String and we need to find the length of the Longest Palindromic Substring.
Let us see a few examples:
Input:
“ZXYFYXAC”
Output:
5
Explanation:
“XYFYX” is the longest palindromic substring of length 5.
Input:
“ABBBBA”
Output:
6
Explanation:
“ABBBBA” is the longest palindromic substring of length 6.
Input:
“XYZA”
Output:
0
Explanation:
There is no palindromic substring of the input String.
APPROACH 1:
We can generate all the substrings of the input String and return the longest palindromic substring among them. We will run two for loops which will tell us the leftmost and rightmost position of the current substring. There will be another inner loop to check if the current substring is a palindrome or not.
Refer to the below implementation of the above approach.
import java.util.*;
class Main{
// This function prints the subString str[low..high]
static void printSubStr(String str, int low, int high)
{
for (int i = low; i <= high; ++i){
System.out.print(str.charAt(i));
}
}
/*
This function prints the
longest palindrome subString
It also returns the length
of the longest palindrome
*/
static int longestPalSubstr(String str)
{
// Get length of input String
int n = str.length();
/*
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.charAt(i + k) != str.charAt(j - k)){
flag = 0;
}
}
// Palindrome
if (flag != 0 && (j - i + 1) > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
System.out.print("Longest palindrome subString is: ");
printSubStr(str, start, start + maxLength - 1);
// return length of LPS
return maxLength;
}
// Driver Code
public static void main(String[] args)
{
String str = "ZXYFYXAC";
System.out.print("\nLength is: "+longestPalSubstr(str));
}
}
Output:
Time Complexity: The time complexity for the above approach is O(N * N * N) because we are running 3 nested for loops in the above approach.
Space Complexity: The space complexity for the above code is O(1) because we are using constant space for this approach.