Apply For Jobs
Get Hiring UpdatesCognizant GenC Elevate Sample Coding Question 3
Question 3
In this article, we will discuss about Coding Question with their solution in C++ java and Python. This is s simple string manipulation questions in which you have to find the longest subsequence length in string s.
Question 3
Rohan and his team are participating in the Treasure Hunt event of college in which in each step they have to solve one problem to get a clue of Treasure location . Rohan’s team has performed very well and reached the final step where they have to provide a code of a problem to get a final clue about treasure .
Given a string s, they need to find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
The string contains only lowercase letters.
Write a program to help Rohan’s team that takes in input as String x and returns the length of the longest palindromic subsequence of x.
Input Specification:
input1: string input
Output Specification:
Return the length of the longest palindromic subsequence
Example 1:
Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.
int max (int x, int y)
{
return (x > y)? x : y;
}
int lps(char *str)
{
int n = strlen(str);
int i, j, cl;
int L[n][n];
for (i = 0; i < n; i++)
L[i][i] = 1;
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
int main()
{
char seq[];
cin>>seq
int n = strlen(seq);
printf ("", lps(seq));
getchar();
return 0;
}
import java.util.*;
public class Main
{
static int max (int x, int y)
{
return (x > y)? x : y;
}
static int lps(String seq)
{
int n = seq.length();
int i, j, cl;
int L[][] = new int[n][n];
for (i = 0; i < n; i++)
L[i][i] = 1;
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (seq.charAt(i) == seq.charAt(j) && cl == 2)
L[i][j] = 2;
else if (seq.charAt(i) == seq.charAt(j))
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
String seq = sc.next();
int n = seq.length();
System.out.println(""+ lps(seq));
}
}
s=input()
n=len(s)
rev = s[::-1]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if s[i-1] == rev[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][n])
