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":
- Possible palindromes: "n","t","iti", "ii", "iii", "iiii", "i","g" "igi" etc
- 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
-
The
maxPalindromicLength
function takes four parameters: the input stringtext
, the starting indexs
, the ending indexe
, and the length of the current palindromelength
. -
The base cases are checked to handle the recursion termination conditions. If
s
becomes equal toe
, it means we have processed the entire substring and it's a palindrome (since a single character is always a palindrome). So, we returnlength + 1
. -
If
s
becomes greater thane
, it means we have considered all possible substrings, and the recursion should stop. In this case, we return the currentlength
. -
If the characters at
text[s]
andtext[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 indexs
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 indexe
to the left, i.e.,maxPalindromicLength(text, s, e - 1, 0)
.
- Case 1: We extend the current palindrome by 2 characters and move to the inner substring by calling
-
If the characters at
text[s]
andtext[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 indexs
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 indexe
to the left, i.e.,maxPalindromicLength(text, s, e - 1, 0)
.
- Case 1: We skip the character at
-
The
lengthOfLPS
function first checks if the length of the input stringtext
is zero. If it's empty, there can't be any palindromic substring, so we return. -
If the string is not empty, we call the
maxPalindromicLength
function with the entire string to find the length of the longest palindromic substring. -
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)
{
LongestPalindrome task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.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
// 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()
{
LongestPalindrome *task = new LongestPalindrome();
// Test
// iiii => 4
task->lengthOfLPS("nitiiiigi");
// ivfvi => 5
task->lengthOfLPS("vvvvivfvim");
// civic => 5
task->lengthOfLPS("xyzacivicxrs");
// opo => 3
task->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
// 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)
{
LongestPalindrome task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.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
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()
{
$task = new LongestPalindrome();
// Test
// iiii => 4
$task->lengthOfLPS("nitiiiigi");
// ivfvi => 5
$task->lengthOfLPS("vvvvivfvim");
// civic => 5
$task->lengthOfLPS("xyzacivicxrs");
// opo => 3
$task->lengthOfLPS("ttoopo");
}
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()
{
var task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
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() :
task = LongestPalindrome()
# Test
# iiii => 4
task.lengthOfLPS("nitiiiigi")
# ivfvi => 5
task.lengthOfLPS("vvvvivfvim")
# civic => 5
task.lengthOfLPS("xyzacivicxrs")
# opo => 3
task.lengthOfLPS("ttoopo")
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()
task = LongestPalindrome.new()
# Test
# iiii => 4
task.lengthOfLPS("nitiiiigi")
# ivfvi => 5
task.lengthOfLPS("vvvvivfvim")
# civic => 5
task.lengthOfLPS("xyzacivicxrs")
# opo => 3
task.lengthOfLPS("ttoopo")
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
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.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
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()
{
let task: LongestPalindrome = LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
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
{
val task: LongestPalindrome = LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.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
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:
- For the input string "nitiiiigi", the longest palindromic substring is "iiii" with a length of 4.
- For the input string "vvvvivfvim", the longest palindromic substring is "ivfvi" with a length of 5.
- For the input string "xyzacivicxrs", the longest palindromic substring is "civic" with a length of 5.
- 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.
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.
New Comment