Skip to main content

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)
    {
        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:

  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.

Last updated on by Kalkicode




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.

New Comment