Posted on by Kalkicode
Code Recursion

Longest palindromic subsequence using recursion

The Longest Palindromic Subsequence (LPS) problem is a classic computer science problem related to finding the longest subsequence of a given string that is also a palindrome. A subsequence is a sequence of characters derived from the original string by deleting zero or more characters without changing the relative order of the remaining characters.

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

The task in the Longest Palindromic Subsequence problem is to find the length of the longest palindromic subsequence in a given string.

Explanation using Example

Let's consider the two test cases from the provided code:

 
    Given  : pewmoozdp
              -   --  -
    Result : 4
    Given  : xbfdsafx
              - -  --- or
              - - - -- or
              - --  -- 
    Result : 5

Test A: text1 = "pewmoozdp"

The longest palindromic subsequence in "pewmoozdp" is "poop", which has a length of 4. Therefore, the output for this test case is 4.

Test B: text2 = "xbfdsafx"

The longest palindromic subsequence in "xbfdsafx" is "xfsfx", "xfdfx", or "xfafx", all of which have a length of 5. Therefore, the output for this test case is 5.

Pseudocode

maxValue(a, b)
    if a > b
        return a
    return b

findLPS(text, start, ends)
    if start == ends
        return 1
    if text[start] == text[ends] and start + 1 == ends
        return 2
    if text[start] == text[ends]
        return findLPS(text, start + 1, ends - 1) + 2
    return maxValue(findLPS(text, start, ends - 1), findLPS(text, start + 1, ends))

Algorithm Explanation

The findLPS function is a recursive algorithm to find the length of the longest palindromic subsequence in a given string. It takes three parameters: text, start, and ends. The variable text represents the input string, while start and ends represent the starting and ending indices of the current substring being processed.

The algorithm starts by checking two base cases:

  1. If start and ends point to the same character (i.e., a single character substring), then the function returns 1, as a single character is a palindrome by itself.
  2. If the characters at start and ends are the same, and they are adjacent (i.e., start + 1 == ends), then the function returns 2, as the two characters form a palindrome.

Next, if the characters at start and ends are the same, the algorithm returns the length of the palindrome formed by excluding the two characters at start and ends, plus 2 (to account for the two characters).

Finally, if the characters at start and ends are different, the algorithm recursively calls itself on two subproblems: one by excluding the character at ends and the other by excluding the character at start. The algorithm then returns the maximum of the two results, representing the length of the longest palindromic subsequence for the current substring.

Code Solution

/*
    C program for
    Longest palindromic subsequence using recursion
*/
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
int findLPS(char *text, int start, int ends)
{
	if (start == ends)
	{
		// When single character remains
		return 1;
	}
	if (text[start] == text[ends] && start + 1 == ends)
	{
		// When two consecutive elements are same character
		return 2;
	}
	if (text[start] == text[ends])
	{
		// Increase start value and reduce end value 
		// and find the recursively  lps
		return findLPS(text, start + 1, ends - 1) + 2;
	}
	return maxValue(findLPS(text, start, ends - 1), findLPS(text, start + 1, ends));
}
int main(int argc, char
	const *argv[])
{
	char *text1 = "pewmoozdp";
	char *text2 = "xbfdsafx";
	// Test A
	int n = strlen(text1);
	// "poop" is resultant palindrome
	// Length 4
	int ans = findLPS(text1, 0, n - 1);
	printf("\n Given  : %s ", text1);
	printf("\n Result : %d", ans);
	// Test B
	n = strlen(text2);
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = findLPS(text2, 0, n - 1);
	printf("\n Given  : %s ", text2);
	printf("\n Result : %d", ans);
	return 0;
}

Output

 Given  : pewmoozdp
 Result : 4
 Given  : xbfdsafx
 Result : 5
/*
    Java program for
    Longest palindromic subsequence using recursion
*/
public class LPS
{
    // Returns the max value of given two numbers
    public int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        return b;
    }
    public int findLPS(String text, int start, int ends)
    {
        if (start == ends)
        {
            // When single character remains
            return 1;
        }
        if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
        {
            // When two consecutive elements are same character
            return 2;
        }
        if (text.charAt(start) == text.charAt(ends))
        {
            // Increase start value and reduce end value 
            // and find the recursively lps
            return findLPS(text, start + 1, ends - 1) + 2;
        }
        return maxValue(findLPS(text, start, ends - 1), 
                        findLPS(text, start + 1, ends));
    }
    public static void main(String[] args)
    {
        LPS task = new LPS();
        String text1 = "pewmoozdp";
        String text2 = "xbfdsafx";
        // Test A
        int n = text1.length();
        // "poop" is resultant palindrome
        // Length 4
        int ans = task.findLPS(text1, 0, n - 1);
        System.out.print("\n Given : " + text1 );
        System.out.print("\n Result : " + ans);
        // Test B
        n = text2.length();
        // [xfsfx,xfdfx,xfafx] is resultant palindrome
        // Length 5
        ans = task.findLPS(text2, 0, n - 1);
        System.out.print("\n Given : " + text2 );
        System.out.print("\n Result : " + ans );

    }
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ program for
    Longest palindromic subsequence using recursion
*/
class LPS
{
	public:
		// Returns the max value of given two numbers
		int maxValue(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			return b;
		}
	int findLPS(string text, int start, int ends)
	{
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text[start] == text[ends] && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text[start] == text[ends])
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return this->findLPS(text, start + 1, ends - 1) + 2;
		}
		return this->maxValue(this->findLPS(text, start, ends - 1), this->findLPS(text, start + 1, ends));
	}
};
int main()
{
	LPS *task = new LPS();
	string text1 = "pewmoozdp";
	string text2 = "xbfdsafx";
	// Test A
	int n = text1.length();
	// "poop" is resultant palindrome
	// Length 4
	int ans = task->findLPS(text1, 0, n - 1);
	cout << "\n Given : " << text1;
	cout << "\n Result : " << ans;
	// Test B
	n = text2.length();
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task->findLPS(text2, 0, n - 1);
	cout << "\n Given : " << text2;
	cout << "\n Result : " << ans;
	return 0;
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
// Include namespace system
using System;
/*
    Csharp program for
    Longest palindromic subsequence using recursion
*/
public class LPS
{
	// Returns the max value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int findLPS(String text, int start, int ends)
	{
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text[start] == text[ends] && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text[start] == text[ends])
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return this.findLPS(text, start + 1, ends - 1) + 2;
		}
		return this.maxValue(this.findLPS(text, start, ends - 1), this.findLPS(text, start + 1, ends));
	}
	public static void Main(String[] args)
	{
		LPS task = new LPS();
		String text1 = "pewmoozdp";
		String text2 = "xbfdsafx";
		// Test A
		int n = text1.Length;
		// "poop" is resultant palindrome
		// Length 4
		int ans = task.findLPS(text1, 0, n - 1);
		Console.Write("\n Given : " + text1);
		Console.Write("\n Result : " + ans);
		// Test B
		n = text2.Length;
		// [xfsfx,xfdfx,xfafx] is resultant palindrome
		// Length 5
		ans = task.findLPS(text2, 0, n - 1);
		Console.Write("\n Given : " + text2);
		Console.Write("\n Result : " + ans);
	}
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
package main
import "fmt"
/*
    Go program for
    Longest palindromic subsequence using recursion
*/

// Returns the max value of given two numbers
func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func findLPS(text string, start int, ends int) int {
	if start == ends {
		// When single character remains
		return 1
	}
	if text[start] == text[ends] && start + 1 == ends {
		// When two consecutive elements are same character
		return 2
	}
	if text[start] == text[ends] {
		// Increase start value and reduce end value 
		// and find the recursively lps
		return findLPS(text, start + 1, ends - 1) + 2
	}
	return maxValue(findLPS(text, start, ends - 1), findLPS(text, start + 1, ends))
}
func main() {

	var text1 string = "pewmoozdp"
	var text2 string = "xbfdsafx"
	// Test A
	var n int = len(text1)
	// "poop" is resultant palindrome
	// Length 4
	var ans int = findLPS(text1, 0, n - 1)
	fmt.Print("\n Given : ", text1)
	fmt.Print("\n Result : ", ans)
	// Test B
	n = len(text2)
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = findLPS(text2, 0, n - 1)
	fmt.Print("\n Given : ", text2)
	fmt.Print("\n Result : ", ans)
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
<?php
/*
    Php program for
    Longest palindromic subsequence using recursion
*/
class LPS
{
	// Returns the max value of given two numbers
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function findLPS($text, $start, $ends)
	{
		if ($start == $ends)
		{
			// When single character remains
			return 1;
		}
		if ($text[$start] == $text[$ends] && $start + 1 == $ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if ($text[$start] == $text[$ends])
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return $this->findLPS($text, $start + 1, $ends - 1) + 2;
		}
		return $this->maxValue($this->findLPS($text, $start, $ends - 1), 
                               $this->findLPS($text, $start + 1, $ends));
	}
}

function main()
{
	$task = new LPS();
	$text1 = "pewmoozdp";
	$text2 = "xbfdsafx";
	// Test A
	$n = strlen($text1);
	// "poop" is resultant palindrome
	// Length 4
	$ans = $task->findLPS($text1, 0, $n - 1);
	echo("\n Given : ".$text1);
	echo("\n Result : ".$ans);
	// Test B
	$n = strlen($text2);
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	$ans = $task->findLPS($text2, 0, $n - 1);
	echo("\n Given : ".$text2);
	echo("\n Result : ".$ans);
}
main();

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
/*
    Node JS program for
    Longest palindromic subsequence using recursion
*/
class LPS
{
	// Returns the max value of given two numbers
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	findLPS(text, start, ends)
	{
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text.charAt(start) == text.charAt(ends))
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return this.findLPS(text, start + 1, ends - 1) + 2;
		}
		return this.maxValue(this.findLPS(text, start, ends - 1), 
                             this.findLPS(text, start + 1, ends));
	}
}

function main()
{
	var task = new LPS();
	var text1 = "pewmoozdp";
	var text2 = "xbfdsafx";
	// Test A
	var n = text1.length;
	// "poop" is resultant palindrome
	// Length 4
	var ans = task.findLPS(text1, 0, n - 1);
	process.stdout.write("\n Given : " + text1);
	process.stdout.write("\n Result : " + ans);
	// Test B
	n = text2.length;
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2, 0, n - 1);
	process.stdout.write("\n Given : " + text2);
	process.stdout.write("\n Result : " + ans);
}
main();

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
#    Python 3 program for
#    Longest palindromic subsequence using recursion
class LPS :
	#  Returns the max value of given two numbers
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		return b
	
	def findLPS(self, text, start, ends) :
		if (start == ends) :
			#  When single character remains
			return 1
		
		if (text[start] == text[ends] and start + 1 == ends) :
			#  When two consecutive elements are same character
			return 2
		
		if (text[start] == text[ends]) :
			#  Increase start value and reduce end value 
			#  and find the recursively lps
			return self.findLPS(text, start + 1, ends - 1) + 2
		
		return self.maxValue(self.findLPS(text, start, ends - 1),
                             self.findLPS(text, start + 1, ends))
	

def main() :
	task = LPS()
	text1 = "pewmoozdp"
	text2 = "xbfdsafx"
	#  Test A
	n = len(text1)
	#  "poop" is resultant palindrome
	#  Length 4
	ans = task.findLPS(text1, 0, n - 1)
	print("\n Given : ", text1, end = "")
	print("\n Result : ", ans, end = "")
	#  Test B
	n = len(text2)
	#  [xfsfx,xfdfx,xfafx] is resultant palindrome
	#  Length 5
	ans = task.findLPS(text2, 0, n - 1)
	print("\n Given : ", text2, end = "")
	print("\n Result : ", ans, end = "")

if __name__ == "__main__": main()

Output

 Given :  pewmoozdp
 Result :  4
 Given :  xbfdsafx
 Result :  5
#    Ruby program for
#    Longest palindromic subsequence using recursion
class LPS 
	#  Returns the max value of given two numbers
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def findLPS(text, start, ends) 
		if (start == ends) 
			#  When single character remains
			return 1
		end

		if (text[start] == text[ends] && start + 1 == ends) 
			#  When two consecutive elements are same character
			return 2
		end

		if (text[start] == text[ends]) 
			#  Increase start value and reduce end value 
			#  and find the recursively lps
			return self.findLPS(text, start + 1, ends - 1) + 2
		end

		return self.maxValue(self.findLPS(text, start, ends - 1), 
                             self.findLPS(text, start + 1, ends))
	end

end

def main() 
	task = LPS.new()
	text1 = "pewmoozdp"
	text2 = "xbfdsafx"
	#  Test A
	n = text1.length
	#  "poop" is resultant palindrome
	#  Length 4
	ans = task.findLPS(text1, 0, n - 1)
	print("\n Given : ", text1)
	print("\n Result : ", ans)
	#  Test B
	n = text2.length
	#  [xfsfx,xfdfx,xfafx] is resultant palindrome
	#  Length 5
	ans = task.findLPS(text2, 0, n - 1)
	print("\n Given : ", text2)
	print("\n Result : ", ans)
end

main()

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
/*
    Scala program for
    Longest palindromic subsequence using recursion
*/
class LPS()
{
	// Returns the max value of given two numbers
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def findLPS(text: String, start: Int, ends: Int): Int = {
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text.charAt(start) == text.charAt(ends))
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return findLPS(text, start + 1, ends - 1) + 2;
		}
		return maxValue(findLPS(text, start, ends - 1), 
                        findLPS(text, start + 1, ends));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LPS = new LPS();
		var text1: String = "pewmoozdp";
		var text2: String = "xbfdsafx";
		// Test A
		var n: Int = text1.length();
		// "poop" is resultant palindrome
		// Length 4
		var ans: Int = task.findLPS(text1, 0, n - 1);
		print("\n Given : " + text1);
		print("\n Result : " + ans);
		// Test B
		n = text2.length();
		// [xfsfx,xfdfx,xfafx] is resultant palindrome
		// Length 5
		ans = task.findLPS(text2, 0, n - 1);
		print("\n Given : " + text2);
		print("\n Result : " + ans);
	}
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
import Foundation;
/*
    Swift 4 program for
    Longest palindromic subsequence using recursion
*/
class LPS
{
	// Returns the max value of given two numbers
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func findLPS(_ text: [Character], _ start: Int, _ ends: Int) -> Int
	{
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text[start] == text[ends] && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text[start] == text[ends])
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return self.findLPS(text, start + 1, ends - 1) + 2;
		}
		return self.maxValue(self.findLPS(text, start, ends - 1),
                             self.findLPS(text, start + 1, ends));
	}
}
func main()
{
	let task: LPS = LPS();
	let text1: String = "pewmoozdp";
	let text2: String = "xbfdsafx";
	// Test A
	var n: Int = text1.count;
	// "poop" is resultant palindrome
	// Length 4
	var ans: Int = task.findLPS(Array(text1), 0, n - 1);
	print("\n Given : ", text1, terminator: "");
	print("\n Result : ", ans, terminator: "");
	// Test B
	n = text2.count;
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(Array(text2), 0, n - 1);
	print("\n Given : ", text2, terminator: "");
	print("\n Result : ", ans, terminator: "");
}
main();

Output

 Given :  pewmoozdp
 Result :  4
 Given :  xbfdsafx
 Result :  5
/*
    Kotlin program for
    Longest palindromic subsequence using recursion
*/
class LPS
{
	// Returns the max value of given two numbers
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun findLPS(text: String, start: Int, ends: Int): Int
	{
		if (start == ends)
		{
			// When single character remains
			return 1;
		}
		if (text.get(start) == text.get(ends) && start + 1 == ends)
		{
			// When two consecutive elements are same character
			return 2;
		}
		if (text.get(start) == text.get(ends))
		{
			// Increase start value and reduce end value 
			// and find the recursively lps
			return this.findLPS(text, start + 1, ends - 1) + 2;
		}
		return this.maxValue(this.findLPS(text, start, ends - 1), this.findLPS(text, start + 1, ends));
	}
}
fun main(args: Array < String > ): Unit
{
	val task: LPS = LPS();
	val text1: String = "pewmoozdp";
	val text2: String = "xbfdsafx";
	// Test A
	var n: Int = text1.length;
	// "poop" is resultant palindrome
	// Length 4
	var ans: Int = task.findLPS(text1, 0, n - 1);
	print("\n Given : " + text1);
	print("\n Result : " + ans);
	// Test B
	n = text2.length;
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2, 0, n - 1);
	print("\n Given : " + text2);
	print("\n Result : " + ans);
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5

Time Complexity

The time complexity of the provided algorithm is exponential, specifically O(2^n), where n is the length of the input string. This is because the algorithm explores all possible subsequences of the input string using recursion, and for each character, there are two possibilities (either include it in the subsequence or exclude it).

Resultant Output Explanation

For Test A with text1 = "pewmoozdp", the algorithm finds the length of the longest palindromic subsequence, which is 4 (e.g., "poop"). The output is 4, which is the expected result.

For Test B with text2 = "xbfdsafx", the algorithm finds the length of the longest palindromic subsequence, which is 5 (e.g., "xfsfx", "xfdfx", or "xfafx"). The output is 5, which is the expected result.

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





Categories
Relative Post