Longest Palindromic Substring
Given a string str, the task is to find the longest substring which is a palindrome.
Examples:
Input: str = “forBeginnerskeegfor”
Output: “Beginnerskeeg”
Explanation: There are several possible palindromic substrings like “kssk”, “ss”, “eeksskee” etc. But the substring “Beginnerskeeg” is the longest among all.Input: str = “Beginner”
Output: “ee”
Naive Approach for Longest Palindromic Substring:
Check each substring, if it is a palindrome or not and keep updating the longest palindromic substring found till now.
Follow the steps mentioned below to implement the idea:
- Generate all the substrings.
- For each substring, check if it is palindrome or not.
- If substring is Palindrome, then update the result on the basis of longest palindromic substring found till now.
Below is the implementation of the above approach:
// A C++ solution for longest palindrome
#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 longestPalSubstr(string str)
{
// Get length of input string
int n = str.size();
// 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;
}
// Driver Code
int main()
{
string str = "forBeginnerskeegfor";
cout << "\nLength is: " << longestPalSubstr(str);
return 0;
}
#include <stdio.h>
#include <string.h>
// Function to print a substring str[low..high]
void printSubStr(const char* str, int low, int high)
{
for (int i = low; i <= high; ++i)
printf("%c", str[i]);
}
// This function prints the longest palindrome substring
// It also returns the length of the longest palindrome
int longestPalSubstr(const char* str)
{
// Get length of input string
int n = strlen(str);
// 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 < n; i++) {
for (int j = i; j < n; 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;
}
}
}
printf("Longest palindrome substring is: ");
printSubStr(str, start, start + maxLength - 1);
printf("\n");
// Return length of LPS
return maxLength;
}
// Driver Code
int main()
{
const char* str = "forBeginnerskeegfor";
printf("Length is: %d\n", longestPalSubstr(str));
return 0;
}
// A Java solution for longest palindrome
import java.util.*;
class GFG {
// Function to print a 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 = "forBeginnerskeegfor";
System.out.print("\nLength is: "
+ longestPalSubstr(str));
}
}
// This code is contributed by shikhasingrajput
# A Python3 solution for longest palindrome
# Function to print a subString str[low..high]
def printSubStr(str, low, high):
for i in range(low, high + 1):
print(str[i], end="")
# This function prints the
# longest palindrome subString
# It also returns the length
# of the longest palindrome
def longestPalSubstr(str):
# Get length of input String
n = len(str)
# All subStrings of length 1
# are palindromes
maxLength = 1
start = 0
# Nested loop to mark start
# and end index
for i in range(n):
for j in range(i, n):
flag = 1
# Check palindrome
for k in range(0, ((j - i) // 2) + 1):
if (str[i + k] != str[j - k]):
flag = 0
# Palindrome
if (flag != 0 and (j - i + 1) > maxLength):
start = i
maxLength = j - i + 1
print("Longest palindrome substring is: ", end="")
printSubStr(str, start, start + maxLength - 1)
# Return length of LPS
return maxLength
# Driver Code
if __name__ == '__main__':
str = "forBeginnerskeegfor"
print("\nLength is:", longestPalSubstr(str))
# This code is contributed by 29AjayKumar
// A C# solution for longest palindrome
using System;
class GFG {
// Function to print a subString str[low..high]
static void printSubStr(String str, int low, int high)
{
for (int i = low; i <= high; ++i)
Console.Write(str[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[i + k] != str[j - k])
flag = 0;
// Palindrome
if (flag != 0 && (j - i + 1) > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
Console.Write("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 = "forBeginnerskeegfor";
Console.Write("\nLength is: "
+ longestPalSubstr(str));
}
}
// This code is contributed by shikhasingrajput
// A Javascript solution for longest palindrome
// Function to print a subString str[low..high]
function printSubStr(str,low,high)
{
for (let i = low; i <= high; ++i)
console.log(str[i]);
}
// This function prints the
// longest palindrome subString
// It also returns the length
// of the longest palindrome
function longestPalSubstr(str)
{
// Get length of input String
let n = str.length;
// All subStrings of length 1
// are palindromes
let maxLength = 1, start = 0;
// Nested loop to mark start and end index
for (let i = 0; i < str.length; i++) {
for (let j = i; j < str.length; j++) {
let flag = 1;
// Check palindrome
for (let k = 0; k < (j - i + 1) / 2; k++)
if (str[i + k] != str[j - k])
flag = 0;
// Palindrome
if (flag!=0 && (j - i + 1) > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
console.log("Longest palindrome substring is: ");
printSubStr(str, start, start + maxLength - 1);
// Return length of LPS
return maxLength;
}
// Driver Code
let str = "forBeginnerskeegfor";
console.log("Length is: "
+ longestPalSubstr(str));
// This code is contributed by rag2127
Output
Longest palindrome substring is: Beginnerskeeg Length is: 10
Complexity Analysis:
- Time complexity: O(N3). Three nested loops are needed to find the longest palindromic substring in this approach.
- Auxiliary complexity: O(1). As no extra space is needed.
Longest Palindromic Substring using Dynamic Programming:
The main idea behind the approach is that if we know the status (i.e., palindrome or not) of the substring ranging [i, j], we can find the status of the substring ranging [i-1, j+1] by only matching the character str[i-1] and str[j+1].
- If the substring from i to j is not a palindrome, then the substring from i-1 to j+1 will also not be a palindrome. Otherwise, it will be a palindrome only if str[i-1] and str[j+1] are the same.
Base on this fact, we can create a 2D table (say table[][] which stores status of substring str[i . . . j] ), and check for substrings with length from 1 to N. For each length find all the substrings starting from each character i and find if it is a palindrom or not using the above idea. The longest length for which a palindrome formed will be the required asnwer.
Illustration:
Follow the below illustration for a better understanding.
Consider the string “Beginner“. Below is the structure of the table formed and from this, we can see that the longest substring is 2.
Follow the steps mentioned below to implement the idea:
- Maintain a boolean table[N][N] that is filled in a bottom-up manner.
- Iterate for all possible lengths from 1 to N:
- For each length iterate from i = 0 to N-length:
- Find the end of the substring j = i+length-1.
- The value of table[i][j] is true, if the substring is palindrome, otherwise false.
- To calculate table[i][j], check the value of table[i+1][j-1]:
- if the value is true and str[i] is the same as str[j], then we make table[i][j] true.
- Otherwise, the value of table[i][j] is made false.
- We have to fill the table initially for substrings of length = 1 and length = 2.
- Update the longest palindrome accordingly whenever a new palindrome of greater length is found.
- For each length iterate from i = 0 to N-length:
Below is the implementation of the above approach:
// A C++ dynamic programming
// solution for longest palindrome
#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 longestPalSubstr(string str)
{
// Get length of input string
int n = str.size();
// 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 sub-string 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 sub-string 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;
}
// Driver Code
int main()
{
string str = "forBeginnerskeegfor";
cout << "\nLength is: "
<< longestPalSubstr(str);
return 0;
}
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
// Function to print a substring str[low..high]
void printSubStr(const char* str, int low, int high)
{
for (int i = low; i <= high; ++i)
printf("%c", str[i]);
}
// This function prints the longest palindrome substring
// It also returns the length of the longest palindrome
int longestPalSubstr(const char* str)
{
// Get length of input string
int n = strlen(str);
// 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, false, sizeof(table));
// All substrings of length 1 are palindromes
int maxLength = 1;
int start = 0;
for (int i = 0; i < n; ++i)
table[i][i] = true;
// Check for sub-string of length 2.
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.
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 sub-string 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;
}
}
}
}
printf("Longest palindrome substring is: ");
printSubStr(str, start, start + maxLength - 1);
printf("\n");
// Return length of LPS
return maxLength;
}
// Driver Code
int main()
{
const char* str = "forBeginnerskeegfor";
printf("Length is: %d\n", longestPalSubstr(str));
return 0;
}
// Java Solution
public class LongestPalinSubstring {
// A utility function to print
// a substring str[low..high]
static void printSubStr(
String str, int low, int high)
{
System.out.println(
str.substring(
low, high + 1));
}
// This function prints the longest
// palindrome substring of str[].
// It also returns the length of the
// longest palindrome
static int longestPalSubstr(String str)
{
// Get length of input string
int n = str.length();
// table[i][j] will be false if
// substring str[i..j] is not palindrome.
// Else table[i][j] will be true
boolean table[][] = new boolean[n][n];
// All substrings of length 1 are palindromes
int maxLength = 1;
for (int i = 0; i < n; ++i)
table[i][i] = true;
// Check for sub-string of length 2.
int start = 0;
for (int i = 0; i < n - 1; ++i) {
if (str.charAt(i) == str.charAt(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 sub-string from ith index to
// jth index if str.charAt(i+1) to
// str.charAt(j-1) is a palindrome
if (table[i + 1][j - 1]
&& str.charAt(i) == str.charAt(j)) {
table[i][j] = true;
if (k > maxLength) {
start = i;
maxLength = k;
}
}
}
}
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 = "forBeginnerskeegfor";
System.out.println("Length is: " + longestPalSubstr(str));
}
}
// This code is contributed by Sumit Ghosh
# Python program
import sys
# A utility function to print a
# substring str[low..high]
def printSubStr(st, low, high):
print ((st[low: high + 1]))
# This function prints the longest palindrome
# substring of st[]. It also returns the length
# of the longest palindrome
def longestPalSubstr(st):
# Get length of input string
n = len(st)
# table[i][j] will be false if substring
# str[i..j] is not palindrome. Else
# table[i][j] will be true
table = [[0 for x in range(n)] for y
in range(n)]
# All substrings of length 1 are
# palindromes
maxLength = 1
i = 0
while (i < n):
table[i][i] = True
i = i + 1
# Check for sub-string of length 2.
start = 0
i = 0
while i < n - 1:
if (st[i] == st[i + 1]):
table[i][i + 1] = True
start = i
maxLength = 2
i = i + 1
# Check for lengths greater than 2.
# k is length of substring
k = 3
while k <= n:
# Fix the starting index
i = 0
while i < (n - k + 1):
# Get the ending index of
# substring from starting
# index i and length k
j = i + k - 1
# Checking for sub-string from
# ith index to jth index if
# st[i + 1] to st[(j-1)] is a
# palindrome
if (table[i + 1][j - 1] and
st[i] == st[j]):
table[i][j] = True
if (k > maxLength):
start = i
maxLength = k
i = i + 1
k = k + 1
print("Longest palindrome substring is: ",end="")
printSubStr(st, start, start + maxLength - 1)
# Return length of LPS
return maxLength
# Driver code
if __name__ == '__main__':
st = "forBeginnerskeegfor"
l = longestPalSubstr(st)
print("Length is:", l)
# This code is contributed by Nikita Tiwari.
// C# code to implement the above idea
using System;
class GFG {
// A utility function to print a
// substring str[low...( high - (low+1))]
static void printSubStr(string str, int low,
int high)
{
Console.WriteLine(str.Substring(low,
high - low + 1));
}
// This function prints the longest
// palindrome substring of str[].
// It also returns the length of the
// longest palindrome
static int longestPalSubstr(string str)
{
// Get length of input string
int n = str.Length;
// Table[i, j] will be false if substring
// str[i..j] is not palindrome. Else
// table[i, j] will be true
bool[, ] table = new bool[n, n];
// All substrings of length 1 are palindromes
int maxLength = 1;
for (int i = 0; i < n; ++i)
table[i, i] = true;
// Check for sub-string 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 sub-string from ith index
// to jth index if str.charAt(i+1) to
// str.charAt(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;
}
}
}
}
Console.Write("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 = "forBeginnerskeegfor";
Console.WriteLine("Length is: " + longestPalSubstr(str));
}
}
// This code is contributed by SoumikMondal
// Javascript Solution
// A utility function to print
// a substring str[low..high]
function printSubStr(str,low,high)
{
console.log(str.substring(low, high + 1));
}
// This function prints the longest
// palindrome substring of str[].
// It also returns the length of the
// longest palindrome
function longestPalSubstr(str)
{
// Get length of input string
let n = str.length;
// table[i][j] will be false if
// substring str[i..j] is not palindrome.
// Else table[i][j] will be true
let table = new Array(n);
for(let i = 0; i < n; i++)
{
table[i] = new Array(n);
}
// All substrings of length 1 are palindromes
let maxLength = 1;
for (let i = 0; i < n; ++i)
table[i][i] = true;
// Check for sub-string of length 2.
let start = 0;
for (let 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 (let k = 3; k <= n; ++k) {
// Fix the starting index
for (let i = 0; i < n - k + 1; ++i)
{
// Get the ending index of substring from
// starting index i and length k
let j = i + k - 1;
// Checking for sub-string from ith index to
// jth index if str.charAt(i+1) to
// str.charAt(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;
}
}
}
}
console.log("Longest palindrome substring is; ");
printSubStr(str, start,
start + maxLength - 1);
// Return length of LPS
return maxLength;
}
// Driver code
let str = "forBeginnerskeegfor";
console.log("Length is: " + longestPalSubstr(str));
// This code is contributed by avanitrachhadiya2155
Output
Longest palindrome substring is: Beginnerskeeg Length is: 10
Time complexity: O(N2). A nested traversal is needed.
Auxiliary Space: O(N2). A matrix of size N*N is needed to store the table.
Longest Palindromic Substring using Expansion from center:
The LPS is either of even length or odd length. So the idea is to traverse the input string and for each character check if this character can be the center of a palindromic substring of odd length or even length.
Follow the steps mentioned below to implement the idea:
- Use two pointers, low and hi, for the left and right end of the current palindromic substring being found.
- Then checks if the characters at str[low] and str[hi] are the same.
- If they are, it expands the substring to the left and right by decrementing low and incrementing hi.
- It continues this process until the characters at str[low] and str[hi] are unequal or until the indices are in bounds.
- If the length of the current palindromic substring becomes greater than the maximum length, it updates the maximum length.
Below is the implementation of the above idea.
// C++ code to implement the above idea
#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];
}
// Function to find the longest palindromic substring
int longestPalSubstr(string s)
{
int n = s.length();
int start = 0, end = 1;
int low, hi;
// Traverse the input string
for (int i = 0; i < n; i++) {
// Find longest palindromic substring of even size
low = i - 1;
hi = i;
// Expand substring while it is palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] == s[hi]) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
// Find longest palindromic substring of odd size
low = i - 1;
hi = i + 1;
// Expand substring while it is palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] == s[hi]) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
}
// Print the longest palindromic substring
cout << "Longest palindrome substring is: ";
printSubStr(s, start, start + end - 1);
// Return output length
return end;
}
// Driver code
int main()
{
string str = "forBeginnerskeegfor";
// Function call
cout << "\nLength is: " << longestPalSubstr(str);
return 0;
}
// This code is contributed by Tapesh(tapeshdua420)
#include <stdio.h>
#include <string.h>
// Function to print a substring str[low..high]
void printSubStr(char str[], int low, int high)
{
for (int i = low; i <= high; ++i)
printf("%c", str[i]);
}
// Function to find the longest palindromic substring
int longestPalSubstr(char s[])
{
int n = strlen(s);
int start = 0, end = 1;
int low, hi;
// Traverse the input string
for (int i = 0; i < n; i++) {
// Find longest palindromic substring of even size
low = i - 1;
hi = i;
// Expand substring while it is palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] == s[hi]) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
// Find longest palindromic substring of odd size
low = i - 1;
hi = i + 1;
// Expand substring while it is palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] == s[hi]) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
}
// Print the longest palindromic substring
printf("Longest palindrome substring is: ");
printSubStr(s, start, start + end - 1);
// Return output length
return end;
}
// Driver code
int main()
{
char str[] = "forBeginnerskeegfor";
// Function call
printf("\nLength is: %d", longestPalSubstr(str));
return 0;
}
class LongestPalinSubstring {
// Function to print a 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));
System.out.println();
}
// Function to find the longest palindromic substring
static int longestPalSubstr(String s) {
int n = s.length();
int start = 0, end = 1;
int low, hi;
// Traverse the input string
for (int i = 0; i < n; i++) {
// Find longest palindromic substring of even size
low = i - 1;
hi = i;
// Expand substring while it is palindrome and in bounds
while (low >= 0 && hi < n && s.charAt(low) == s.charAt(hi)) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
// Find longest palindromic substring of odd size
low = i - 1;
hi = i + 1;
// Expand substring while it is palindrome and in bounds
while (low >= 0 && hi < n && s.charAt(low) == s.charAt(hi)) {
// Update maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
}
// Print the longest palindromic substring
System.out.print("Longest palindrome substring is: ");
printSubStr(s, start, start + end - 1);
// Return output length
return end;
}
// Driver code
public static void main(String[] args) {
String s = "forBeginnerskeegfor";
int length = longestPalSubstr(s);
System.out.println("Length: " + length);
}
}
def printSubStr(s, low, high):
for i in range(low, high + 1):
print(s[i], end="")
print()
def longestPalSubstr(s):
n = len(s)
start = 0
end = 1
for i in range(n):
# Find the longest palindromic substring of even length
low = i - 1
hi = i
while low >= 0 and hi < n and s[low] == s[hi]:
if hi - low + 1 > end:
start = low
end = hi - low + 1
low -= 1
hi += 1
# Find the longest palindromic substring of odd length
low = i - 1
hi = i + 1
while low >= 0 and hi < n and s[low] == s[hi]:
if hi - low + 1 > end:
start = low
end = hi - low + 1
low -= 1
hi += 1
# Print the longest palindromic substring
print("Longest palindrome substring is: ", end="")
printSubStr(s, start, start + end - 1)
# Return the length of the longest palindromic substring
return end
# Driver Code:
if __name__=='__main__':
s="forBeginnerskeegfor"
length = longestPalSubstr(s)
print("Length:", length)
# Code Contributed by atharvajadhav11
using System;
class GFG {
// Function to print a substring
static void PrintSubStr(string s, int low, int high)
{
for (int i = low; i <= high; i++) {
Console.Write(s[i]);
}
Console.WriteLine();
}
// Function to find the longest palindromic substring
static int LongestPalSubstr(string s)
{
int n = s.Length;
int start = 0;
int end = 1;
for (int i = 0; i < n; i++) {
// Find the longest palindromic substring of
// even length
int low = i - 1;
int hi = i;
while (low >= 0 && hi < n && s[low] == s[hi]) {
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
// Find the longest palindromic substring of odd
// length
low = i - 1;
hi = i + 1;
while (low >= 0 && hi < n && s[low] == s[hi]) {
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
}
// Print the longest palindromic substring
Console.Write("Longest palindrome substring is: ");
PrintSubStr(s, start, start + end - 1);
// Return the length of the longest palindromic
// substring
return end;
}
// Driver Code:
static void Main()
{
string s = "forBeginnerskeegfor";
int length = LongestPalSubstr(s);
Console.WriteLine("Length: " + length);
}
}
// Function to print a substring str[low..high]
function printSubStr(str, low, high) {
for (let i = low; i <= high; ++i) {
console.log(str[i]);
}
}
// Function to find the longest palindromic substring
function longestPalSubstr(s) {
const n = s.length;
let start = 0, end = 1;
let low, hi;
// Traverse the input string
for (let i = 0; i < n; i++) {
// Find the longest palindromic substring of even size
low = i - 1;
hi = i;
// Expand substring while it is a palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] === s[hi]) {
// Update the maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
// Find the longest palindromic substring of odd size
low = i - 1;
hi = i + 1;
// Expand substring while it is a palindrome
// and in bounds
while (low >= 0 && hi < n && s[low] === s[hi]) {
// Update the maximum length and starting index
if (hi - low + 1 > end) {
start = low;
end = hi - low + 1;
}
low--;
hi++;
}
}
// Print the longest palindromic substring
console.log("Longest palindrome substring is: ");
printSubStr(s, start, start + end - 1);
// Return the output length
return end;
}
const str = "forBeginnerskeegfor";
console.log("\nLength is: " + longestPalSubstr(str));
Output
Longest palindrome substring is: Beginnerskeeg Length is: 10
Time complexity: O(N2), where N is the length of the input string
Auxiliary Space: O(1), No extra space used.