Posted on by Kalkicode
Code Recursion

# Longest palindromic substring recursive

The given problem is to find the length of the longest palindromic substring in a given string using a recursive approach. A palindrome is a sequence of characters that reads the same backward as forward. The task is to find the longest palindrome in the given string and return its length.

## Example:

Let's take the example of the string "nitiiiigi":

1. Possible palindromes: "n","t","iti", "ii", "iii", "iiii", "i","g" "igi" etc
2. The longest palindrome is "iiii" with a length of 4.

## Pseudocode

Before diving into the recursive algorithm, let's outline the pseudocode for better understanding:

``````function maxPalindromicLength(text, s, e, length):
if s == e:
return length + 1
if s > e:
return length
if text[s] == text[e]:
return max(
maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)
)
else:
return max(
maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)
)

function lengthOfLPS(text):
n = length of text
if n == 0:
return
length = maxPalindromicLength(text, 0, n - 1, 0)
return length
``````

## Algorithm Explanation

1. The `maxPalindromicLength` function takes four parameters: the input string `text`, the starting index `s`, the ending index `e`, and the length of the current palindrome `length`.

2. The base cases are checked to handle the recursion termination conditions. If `s` becomes equal to `e`, it means we have processed the entire substring and it's a palindrome (since a single character is always a palindrome). So, we return `length + 1`.

3. If `s` becomes greater than `e`, it means we have considered all possible substrings, and the recursion should stop. In this case, we return the current `length`.

4. If the characters at `text[s]` and `text[e]` are the same, we have a possibility of a longer palindrome. We then explore three cases using recursion:

• Case 1: We extend the current palindrome by 2 characters and move to the inner substring by calling `maxPalindromicLength(text, s + 1, e - 1, length + 2)`.
• Case 2: We skip the character at `s` and try to find a palindrome by moving the starting index `s` to the right, i.e., `maxPalindromicLength(text, s + 1, e, 0)`.
• Case 3: We skip the character at `e` and try to find a palindrome by moving the ending index `e` to the left, i.e., `maxPalindromicLength(text, s, e - 1, 0)`.
5. If the characters at `text[s]` and `text[e]` are not the same, we can't form a palindrome with the current characters. So, we explore two cases:

• Case 1: We skip the character at `s` and try to find a palindrome by moving the starting index `s` to the right, i.e., `maxPalindromicLength(text, s + 1, e, 0)`.
• Case 2: We skip the character at `e` and try to find a palindrome by moving the ending index `e` to the left, i.e., `maxPalindromicLength(text, s, e - 1, 0)`.
6. The `lengthOfLPS` function first checks if the length of the input string `text` is zero. If it's empty, there can't be any palindromic substring, so we return.

7. If the string is not empty, we call the `maxPalindromicLength` function with the entire string to find the length of the longest palindromic substring.

8. The `maxPalindromicLength` function is called recursively to explore different substrings, and finally, it returns the length of the longest palindrome.

## Program Solution

``````/*
C program for
Longest palindromic substring recursive
*/
#include <stdio.h>
#include <string.h>

int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int maxLength(char *text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(
maxLength(text, s + 1, e - 1, length + 2),
maxValue(maxLength(text, s + 1, e, 0),
maxLength(text, s, e - 1, 0)));
}
return maxValue(maxLength(text, s + 1, e, 0),
maxLength(text, s, e - 1, 0));
}
void lengthOfLPS(char *text)
{
// Get length of text
int n = strlen(text);
if (n == 0)
{
// When text is empty
return;
}
// Display given text
printf("\n Given string : %s", text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = maxLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
printf("\n Resultant palindrome length : %d", length);
}
int main(int argc, char
const *argv[])
{
// Test
// iiii => 4
lengthOfLPS("nitiiiigi");
// ivfvi => 5
lengthOfLPS("vvvvivfvim");
// civic => 5
lengthOfLPS("xyzacivicxrs");
// opo => 3
lengthOfLPS("ttoopo");
return 0;
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````// Java program for
// Longest palindromic substring recursive
public class LongestPalindrome
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxPalindromicLength(String text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)));
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0));
}

public void lengthOfLPS(String text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
System.out.print("\n Given string : " + text );
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
System.out.print("\n Resultant palindrome length : " + length );
}
public static void main(String[] args)
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
// C++ program for
// Longest palindromic substring recursive
class LongestPalindrome
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int maxPalindromicLength(string text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this->maxValue(
this->maxPalindromicLength(text, s + 1, e - 1, length + 2),
this->maxValue(this->maxPalindromicLength(text, s + 1, e, 0),
this->maxPalindromicLength(text, s, e - 1, 0)));
}
return this->maxValue(this->maxPalindromicLength(text, s + 1, e, 0),
this->maxPalindromicLength(text, s, e - 1, 0));
}
void lengthOfLPS(string text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
cout << "\n Given string : " << text;
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = this->maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
cout << "\n Resultant palindrome length : " << length;
}
};
int main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
return 0;
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````// Include namespace system
using System;
// Csharp program for
// Longest palindromic substring recursive
public class LongestPalindrome
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxPalindromicLength(String text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
public void lengthOfLPS(String text)
{
// Get length of text
int n = text.Length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
Console.Write("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
Console.Write("\n Resultant palindrome length : " + length);
}
public static void Main(String[] args)
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````package main
import "fmt"
// Go program for
// Longest palindromic substring recursive

func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func maxPalindromicLength(text string, s int, e int, length int) int {
if s == e {
return length + 1
}
if s > e {
return length
}
if text[s] == text[e] {
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)))
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0))
}
func lengthOfLPS(text string) {
// Get length of text
var n int = len(text)
if n == 0 {
// When text is empty
return
}
// Display given text
fmt.Print("\n Given string : ", text)
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length int = maxPalindromicLength(text, 0, n - 1, 0)
// Display length of resultant palindrome
fmt.Print("\n Resultant palindrome length : ", length)
}
func main() {

// Test
// iiii => 4
lengthOfLPS("nitiiiigi")
// ivfvi => 5
lengthOfLPS("vvvvivfvim")
// civic => 5
lengthOfLPS("xyzacivicxrs")
// opo => 3
lengthOfLPS("ttoopo")
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````<?php
// Php program for
// Longest palindromic substring recursive
class LongestPalindrome
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function maxPalindromicLength(\$text, \$s, \$e, \$length)
{
if (\$s == \$e)
{
return \$length + 1;
}
if (\$s > \$e)
{
return \$length;
}
if (\$text[\$s] == \$text[\$e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return \$this->maxValue(
\$this->maxPalindromicLength(\$text, \$s + 1, \$e - 1, \$length + 2),
\$this->maxValue(\$this->maxPalindromicLength(\$text, \$s + 1, \$e, 0),
\$this->maxPalindromicLength(\$text, \$s, \$e - 1, 0)));
}
return \$this->maxValue(\$this->maxPalindromicLength(\$text, \$s + 1, \$e, 0),
\$this->maxPalindromicLength(\$text, \$s, \$e - 1, 0));
}
public	function lengthOfLPS(\$text)
{
// Get length of text
\$n = strlen(\$text);
if (\$n == 0)
{
// When text is empty
return;
}
// Display given text
echo("\n Given string : ".\$text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
\$length = \$this->maxPalindromicLength(\$text, 0, \$n - 1, 0);
// Display length of resultant palindrome
echo("\n Resultant palindrome length : ".\$length);
}
}

function main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````// Node JS program for
// Longest palindromic substring recursive
class LongestPalindrome
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maxPalindromicLength(text, s, e, length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
lengthOfLPS(text)
{
// Get length of text
var n = text.length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
process.stdout.write("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
process.stdout.write("\n Resultant palindrome length : " + length);
}
}

function main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````#  Python 3 program for
#  Longest palindromic substring recursive
class LongestPalindrome :
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def maxPalindromicLength(self, text, s, e, length) :
if (s == e) :
return length + 1

if (s > e) :
return length

if (text[s] == text[e]) :
#  When boundary element are similar.
#  Find the palindrome length in possible three cases.
#  Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0)))

return self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))

def lengthOfLPS(self, text) :
#  Get length of text
n = len(text)
if (n == 0) :
#  When text is empty
return

#  Display given text
print("\n Given string : ", text, end = "")
#  1st parameters are passing text
#  2nd parameter is start point
#  3rd parameter is last point
#  4th is resultant length
length = self.maxPalindromicLength(text, 0, n - 1, 0)
#  Display length of resultant palindrome
print("\n Resultant palindrome length : ", length, end = "")

def main() :
#  Test
#  iiii => 4
#  ivfvi => 5
#  civic => 5
#  opo => 3

if __name__ == "__main__": main()``````

#### Output

`````` Given string :  nitiiiigi
Resultant palindrome length :  4
Given string :  vvvvivfvim
Resultant palindrome length :  5
Given string :  xyzacivicxrs
Resultant palindrome length :  5
Given string :  ttoopo
Resultant palindrome length :  3``````
``````#  Ruby program for
#  Longest palindromic substring recursive
class LongestPalindrome
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def maxPalindromicLength(text, s, e, length)
if (s == e)
return length + 1
end

if (s > e)
return length
end

if (text[s] == text[e])
#  When boundary element are similar.
#  Find the palindrome length in possible three cases.
#  Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))
)
end

return self.maxValue(
self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))
end

def lengthOfLPS(text)
#  Get length of text
n = text.length
if (n == 0)
#  When text is empty
return
end

#  Display given text
print("\n Given string : ", text)
#  1st parameters are passing text
#  2nd parameter is start point
#  3rd parameter is last point
#  4th is resultant length
length = self.maxPalindromicLength(text, 0, n - 1, 0)
#  Display length of resultant palindrome
print("\n Resultant palindrome length : ", length)
end

end

def main()
#  Test
#  iiii => 4
#  ivfvi => 5
#  civic => 5
#  opo => 3
end

main()``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````import scala.collection.mutable._;
// Scala program for
// Longest palindromic substring recursive
class LongestPalindrome()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maxPalindromicLength(
text: String,
s: Int,
e: Int,
length: Int): Int = {
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(
maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)));
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0), maxPalindromicLength(text, s, e - 1, 0));
}
def lengthOfLPS(text: String): Unit = {
// Get length of text
var n: Int = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length: Int = maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : " + length);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LongestPalindrome = new LongestPalindrome();
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````
``````import Foundation;
// Swift 4 program for
// Longest palindromic substring recursive
class LongestPalindrome
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maxPalindromicLength(_ text: [Character],
_ s: Int,
_ e: Int,
_ length: Int) -> Int
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0)));
}
return self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0));
}
func lengthOfLPS(_ text: String)
{
// Get length of text
let n: Int = text.count;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : ", text, terminator: "");
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
let length: Int = self.maxPalindromicLength(Array(text), 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : ", length, terminator: "");
}
}
func main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();``````

#### Output

`````` Given string :  nitiiiigi
Resultant palindrome length :  4
Given string :  vvvvivfvim
Resultant palindrome length :  5
Given string :  xyzacivicxrs
Resultant palindrome length :  5
Given string :  ttoopo
Resultant palindrome length :  3``````
``````// Kotlin program for
// Longest palindromic substring recursive
class LongestPalindrome
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maxPalindromicLength(text: String, s: Int, e: Int, length: Int): Int
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.get(s) == text.get(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
fun lengthOfLPS(text: String): Unit
{
// Get length of text
val n: Int = text.length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
val length: Int = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : " + length);
}
}
fun main(args: Array < String > ): Unit
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}``````

#### Output

`````` Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3``````

## Time Complexity

The time complexity of the given recursive approach can be quite high because it explores many overlapping subproblems. For each pair of indices `(s, e)`, the function tries all possible pairs `(s + 1, e - 1)`, `(s + 1, e)`, and `(s, e - 1)`.

Let `n` be the length of the input string. In the worst case, the function explores all possible combinations, which leads to an exponential time complexity of O(3^n).

## Resultant Output Explanation

The given code provides the length of the longest palindromic substring for each test case:

1. For the input string "nitiiiigi", the longest palindromic substring is "iiii" with a length of 4.
2. For the input string "vvvvivfvim", the longest palindromic substring is "ivfvi" with a length of 5.
3. For the input string "xyzacivicxrs", the longest palindromic substring is "civic" with a length of 5.
4. For the input string "ttoopo", the longest palindromic substring is "opo" with a length of 3.

The code uses the recursive algorithm to find the length of the longest palindromic substring for each test case and displays the results accordingly. However, due to the high time complexity of the recursive approach, it is not an efficient solution for large input strings. In such cases, a dynamic programming approach can be used to optimize the solution.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post