Longest Palindromic Subsequence – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Longest Palindromic Subsequence HackerRank Solution
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 3005;
int dp[SIZE][SIZE];
int dp2[SIZE][SIZE];
char s[SIZE];
int main(){
CASET{
DRII(n,K);
RS(s+1);
if(K>2)puts("0");
else if(K==0){
printf("%d\n",n*26+26);
}
else{
MS0(dp);
MS0(dp2);
REPP(i,1,n+1)dp2[i][i]=1;
REPP(j,1,n){
for(int k=1;k+j<=n;k++){
int ll=k,rr=k+j;
if(s[ll]==s[rr])dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr-1]+2);
dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr]);
dp2[ll][rr]=max(dp2[ll][rr],dp2[ll][rr-1]);
}
}
int ma=0;
for(int i=1;i<n;i++){
for(int j=n;j>i;j--){
if(s[i]==s[j])dp[i][j]=dp[i-1][j+1]+2;
else dp[i][j]=max(dp[i-1][j],dp[i][j+1]);
ma=max(ma,dp[i][j]);
}
}
REPP(i,1,n+1)ma=max(ma,dp[i-1][i+1]+1);
int an=0;
REP(i,n+1){
int me=0;
me=dp[i][i+1]+1;
if(me>=ma+K){
an+=26;
continue;
}
bool used[26]={};
REPP(j,1,n+1){
if(j<=i){
if(dp2[j+1][i]+dp[j-1][i+1]+2>=ma+K)used[s[j]-'a']=1;
}
else{
if(dp2[i+1][j-1]+dp[i][j+1]+2>=ma+K)used[s[j]-'a']=1;
}
}
REP(j,26)
if(used[j]){
an++;
}
}
printf("%d\n",an);
}
}
return 0;
}
Java Longest Palindromic Subsequence HackerRank Solution
import java.util.Scanner;
/**
*
* @author abhishek
*/
public class LongestPalSeq {
//lsc[i][j] = length of longest common subsequence between S[0,i] and rev(S)[0,j] i.e. S[n-1-j]
private static int[][] lcs(char[] arr,char[] b){
int[][] lcs = new int[arr.length+1][b.length+1];
int i,j;
for(i=1;i<=arr.length;i++){
for(j=1;j<=b.length;j++){
if(arr[i-1] == b[j-1]){
lcs[i][j] = 1+lcs[i-1][j-1];
}
else{
lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);
}
}
}
return lcs;
}
//lps[i][j] = maximumlength of any palindrome in S[i][j]
private static int[][] calcLPS(char[] arr){
int[][] lps = new int[arr.length][arr.length];
int i,j,k;
for(i=0;i<arr.length;i++){
lps[i][i] = 1;
}
//k denotes the length of substring
//all 1 length are have already been covered
for(k=2;k<=arr.length;k++){
for(i=0;i<=arr.length-k;i++){
j = i+k-1;
if(j==i+1){
//i.e. only two characters
if(arr[i]==arr[j]){
lps[i][j] = 2;
}
else{
lps[i][j] = 1;
}
}
else{
if(arr[i] == arr[j]){
lps[i][j] = 2+lps[i+1][j-1];
}
else{
lps[i][j] = Math.max(lps[i+1][j],lps[i][j-1]);
}
}
}
}
return lps;
}
private static int calcWays(int[][] lps,int[][] lcs,char[] arr,int lp){
int n = arr.length;
int i,j,k;
int ans = 0;
//there are n+1 positions to insert a new character
//also length of palindrome cannot be increased more than 2
//we will try to put character at each of these positions and try to
//get the length of palindrome, if it increases then we add this to final answer
int[] table = new int[26];
//i denotes the position of new character will be added
//just assuming strings from index 1 for lcs
for(i=0;i<=arr.length;i++){
//consider i as a center, then new pal will always be of odd length
int x = Math.max(lps[0][n-1], 1+lcs[i][n-i]*2);
for(k=0;k<=25;k++){
table[k] = x;
}
//consider the case when i is not the center
for(j=0;j<arr.length;j++){
if(j<i){
x = lcs[j][n-i]*2+(j+1<n?lps[j+1][i-1]:0);
}
else if(j>i){
x = lcs[i][n-j-1]*2 + lps[i][j-1];
}
else{
x = lcs[i][n-j-1]*2;
}
table[arr[j]-'a'] = Math.max(table[arr[j]-'a'], (x+2));
}
for(j=0;j<=25;j++){
if(table[j] >= lps[0][n-1]+lp){
ans++;
}
}
}
return ans;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int i,t,k,n;
t = scan.nextInt();
for(i=0;i<t;i++){
n = scan.nextInt();
k = scan.nextInt();
char[] arr = scan.next().toCharArray();
if(k == 0){
System.out.println((26*(n+1)));
}
else if(n == 1){
System.out.println(2);
}
else{
int[][] lps = calcLPS(arr);
int[][] lcs = lcs(arr,reverse(arr));
int ans = calcWays(lps,lcs,arr,k);
System.out.println(ans);
}
/*for(int i=0;i<lcs.length;i++){
for(int j=0;j<lcs.length;j++){
System.out.print(lcs[i][j] + " ");
}
System.out.println();
}*/
}
}
private static char[] reverse(char[] arr){
char[] rev = new char[arr.length];
int i,n= arr.length-1;
for(i=0;i<=n;i++){
rev[i] = arr[n-i];
}
return rev;
}
}
Python 3 Longest Palindromic Subsequence HackerRank Solution
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the longestPalindromicSubsequence function below.
def max(x, y):
if(x > y):
return x
return y
def stripwordfromsameletters(str):
if len(str) > 1:
el1 = ""
i = 0
for el in str:
found = False
for rel in str[i + 1:]:
if el == rel:
found = True
break
i += 1
if not found:
el1 += el
return el1
return str
def append_if_not_find(arr, e):
for a in arr:
if e == a:
return arr
arr += e
return arr
def content_combinations(ltr_pos_ar, st, beg, end, k):
cont = st[beg+1:end]
length = len(cont)
if length < 2 and k == 2:
return True
if length == 0 and k == 1:
for i in range(97, 123):
ltr_pos_ar[beg + 1] = append_if_not_find(ltr_pos_ar[beg + 1], chr(i))
return True
if length > 0 and k == 1:
for i in range(length):
for j in range(length + 1):
ltr_pos_ar[beg + j + 1] = append_if_not_find(ltr_pos_ar[beg + j + 1], cont[i])
return True
for i in range(length):
for j in range(length):
if j > i:
ltr_pos_ar[beg + j + 2] = append_if_not_find(ltr_pos_ar[beg + j + 2], cont[i])
elif i > j:
ltr_pos_ar[beg + j + 1] = append_if_not_find(ltr_pos_ar[beg + j + 1], cont[i])
return True
def edge_combinations(ltr_pos_ar, st, left_beg, left_end, right_beg, right_end, k):
edgeleft = st[left_beg:left_end]
edgeright = st[right_beg:right_end]
stredgeleft = stripwordfromsameletters(edgeleft)
if k == 1 and right_beg - left_end == 2:
content_combinations(ltr_pos_ar, st, left_beg - 1, left_end, 2)
stredgeleft += st[left_end + 1]
for ll in stredgeleft:
ltr_pos_ar[right_beg] = append_if_not_find(ltr_pos_ar[right_beg], ll)
for i in range(len(edgeright)):
ltr_pos_ar[right_beg + i + 1] = append_if_not_find(ltr_pos_ar[right_beg + i + 1], ll)
stredgeright = stripwordfromsameletters(edgeright)
if k == 1 and right_beg - left_end == 2:
content_combinations(ltr_pos_ar, st, right_beg - 1, right_end, 2)
stredgeright += st[right_beg - 2]
for rl in stredgeright:
ltr_pos_ar[left_end] = append_if_not_find(ltr_pos_ar[left_end], rl)
for i in range(len(edgeleft)):
ltr_pos_ar[left_end - i - 1] = append_if_not_find(ltr_pos_ar[left_end - i - 1], rl)
return True
def lps(ae, st, n, k):
# Create a table to store results of sub problems
L = [[0 for x in range(n)] for x in range(n)]
# Strings of length 1 are palindrome of length 1
for i in range(n):
L[i][i] = 1
for cl in range(2, n + 1):
# cl = current subsequence length
for i in range(n - cl + 1):
# j = last character
j = i + cl - 1
if st[i] == st[j]:
# if first and last characters of the substring are the same
if cl == 2:
L[i][j] = 2
else:
L[i][j] = L[i + 1][j - 1] + 2
# pl = current longest palindromic sequence
pl = L[i][j]
if pl - len(ae) >= 2:
# if current longest palindromic is greater plus 2 than the ea list then it fills it with
# default
for ln in range(len(ae), pl - 1):
ae.append({"pl": ln + 2, "ea": []})
kid = []
if pl > 3:
for ie in range(len(ae[pl - 4]['ea'])):
e = ae[pl - 4]['ea'][ie]
if e['beg'] > i and e['end'] < j:
kid.append({"idx": ie, "pl": pl - 4, "k": k})
if k == 1:
if pl > 4:
for ie in range(len(ae[pl - 5]['ea'])):
e = ae[pl - 5]['ea'][ie]
if e['beg'] > i and e['end'] < j:
kid.append({"idx": ie, "pl": pl - 5, "k": 2})
ae[pl - 2]['ea'].append({"beg": i, "end": j, "kid": kid, "prn": {}, "nxt": {}, "pl": pl-2})
else:
L[i][j] = max(L[i][j - 1], L[i + 1][j])
return L[0][n - 1]
def getways(ltr_pos_ar, ae, st, n, k):
scount = 0
if len(ae) == 0:
# if the string contains no double letters
content_combinations(ltr_pos_ar, st, -1, n, k)
for x in ltr_pos_ar:
scount += len(x)
return scount
# get the element from the ae array with the longest palindromic number
prn_pl = len(ae) + 1
pl = len(ae) - 1
ple = ae[pl]
ge = ple['ea']
len_ge = len(ge)
e, pl = ge[0], ple['pl'] - 2
e['kid_idx'], e['k'] = 0, k
ck = k
root_kid = [{"idx": 0, "pl": pl, "k": ck}]
if len_ge > 1:
# if it has siblings
for ie in range(len(ge[:len_ge - 1])):
coord = {"idx": ie + 1, "pl": pl, "k": k}
ge[ie]['nxt'] = coord
ge[ie + 1]['kid_idx'] = ie + 1
root_kid.append(coord)
if k == 1 and len(ae) > 1:
# if k =1 and ae is over 1
el = len(ae) - 2
ple = ae[el]
ge = ple['ea']
len_ge = len(ge)
if len_ge > 0:
len_kid = len(root_kid)
last_kid_e = root_kid[len_kid - 1]
last_kid_pl = last_kid_e['pl']
last_kid_idx = last_kid_e['idx']
last_kid = ae[last_kid_pl]['ea'][last_kid_idx]
coord = {"idx": 0, "pl": el, "k": 2}
last_kid['nxt'] = coord
ge[0]['kid_idx'] = len_kid
root_kid.append(coord)
for ie in range(len(ge[:len_ge - 1])):
coord = {"idx": ie + 1, "pl": pl - 1, "k": 2}
ge[ie]['nxt'] = coord
ge[ie + 1]['kid_idx'] = ie + len_kid + 1
root_kid.append(coord)
# left, right = st[:e['beg']], st[e['end'] + 1:]
nxt, kid = e['nxt'], e['kid']
prn, idx = {}, 0
if pl <= 1:
# if longest palindromic is 3 compute the inner substring inside the string: x..in..x
e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], ck)
# Compute the outer, left and right substrings of the string: left..x..in..x..right
edge_combinations(ltr_pos_ar, st, 0, e['beg'], e['end'] + 1, len(st), ck)
# print(f" FIRST LEVEL:{pl} k:{k} {e}")
# print(ltr_pos_ar)
proceed = True
prn_beg = -1
prn_end = len(st)
prn_kid = root_kid
while proceed:
if len(kid) > 0:
# if it has children go to first child
prn_kid = kid
# prn_idx = e['kid_idx']
ck = e['k']
prn_pl = e['pl']
prn_beg, prn_end = e['beg'], e['end']
pl = kid[0]['pl']
ple = ae[pl]
ge = ple['ea']
e = ge[kid[0]['idx']]
e['kid_idx'], e['prn'] = 0, {'pl': prn_pl, 'idx': idx}
idx = kid[0]['idx']
if len(prn_kid) > 1:
# if it is in turn not the last kid create a reference to its sibling
coord_next = prn_kid[1]
e['nxt'] = coord_next
ae[coord_next['pl']]['ea'][coord_next['idx']]['kid_idx'] = 1
else:
e['nxt'] = {}
# left = st[prnbeg + 1:e['beg']]
# right = st[e['end'] + 1:prnend]
if prn_pl - pl == 3:
if k == 1 and ck == 2:
# if parent k = 2 and app k = 1 and difference = 3 then halt the loop
e['kid'] = []
prn = e['prn']
nxt = e['nxt']
kid = e['kid']
continue
ck = 2
e['k'] = ck
if pl <= 1 and 'cc' not in e:
# if longest palindromic is 3 compute the inner substring inside the string: x..in..x
e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], e['k'])
# Compute the outer, left and right substrings of the string: left..x..in..x..right
edge_combinations(ltr_pos_ar, st, prn_beg + 1, e['beg'], e['end'] + 1, prn_end, e['k'])
# print(f" CHILD LEVEL:{pl} k:{ck} {e}")
# print(ltr_pos_ar)
elif nxt != {}:
# if it has siblings go to next sibling
pl = nxt['pl']
ple = ae[pl]
ge = ple['ea']
e = ge[nxt['idx']]
e['prn'] = prn
idx = nxt['idx']
if len(prn_kid) > e['kid_idx'] + 1:
# if it is in turn not the last kid then create a reference to its sibling
coord_next = prn_kid[e['kid_idx'] + 1]
e['nxt'] = coord_next
ae[coord_next['pl']]['ea'][coord_next['idx']]['kid_idx'] = e['kid_idx'] + 1
else:
e['nxt'] = {}
# left = st[prnbeg + 1:e['beg']]
# right = st[e['end'] + 1:prnend]
if prn_pl - pl == 3:
if k == 1 and ck == 2:
# if parent k = 2 and app k = 1 and difference = 3 then halt the loop
e['kid'] = []
prn = e['prn']
nxt = e['nxt']
kid = e['kid']
continue
ck = 2
e['k'] = ck
if pl <= 1 and 'cc' not in e:
# if longest palindromic is 3 compute the inner substring inside the string: x..in..x
e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], e['k'])
# Compute the outer, left and right substrings of the string: left..x..in..x..right
edge_combinations(ltr_pos_ar, st, prn_beg + 1, e['beg'], e['end'] + 1, prn_end, e['k'])
# print(f" NEXT LEVEL:{pl} k:{e['k']} {e}")
# print(ltr_pos_ar)
elif prn != {}:
pl = prn['pl']
ple = ae[pl]
kid_idx = e['kid_idx']
e = ple['ea'][prn['idx']]
if kid_idx == len(e['kid']) - 1:
# if is the last kid
e['kid'] = []
if e['prn'] != {}:
prn_pl = e['prn']['pl']
ple = ae[prn_pl]
ep = ple['ea'][e['prn']['idx']]
prn_beg = ep['beg']
prn_end = ep['end']
prn_kid = ep['kid']
ck = ep['k']
else:
prn_beg = -1
prn_end = len(st)
prn_kid = root_kid
prn_pl = len(ae) + 1
ck = k
# print(f" PARENT BACK LEVEL:{pl} k:{e['k']} {e}")
prn = e['prn']
nxt = e['nxt']
kid = e['kid']
proceed = not (nxt == {} and len(kid) == 0 and prn == {})
# print(ltr_pos_ar)
# Iterate the array
for x in ltr_pos_ar:
scount += len(x)
# print(f"scount: {scount}")
return scount
def longestPalindromicSubsequence(st, k):
global n
ways = 0
if k == 0:
return 26 * (n + 1)
if k >= 3:
return 0
ae = []
slong = lps(ae, st, n, k)
# print(f"longest current palindromic for string {s} is: {slong}")
ltr_pos_ar = ['' for i in range(n + 1)]
ways = getways(ltr_pos_ar, ae, st, n, k)
return ways
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
q = int(input())
for q_itr in range(q):
nk = input().split()
n = int(nk[0])
k = int(nk[1])
s = input()
result = longestPalindromicSubsequence(s, k)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 Longest Palindromic Subsequence HackerRank Solution
C Longest Palindromic Subsequence HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int x,int y);
int solve1(int x,int y);
int solve2(int x,int y);
char str[3001];
int dp1[3000][3000],dp2[3000][3000],b[26][3001],n;
int main(){
int q,ans,i,j,k,l;
scanf("%d",&q);
while(q--){
memset(dp1,-1,sizeof(dp1));
memset(dp2,-1,sizeof(dp2));
for(i=ans=0;i<26;i++)
b[i][0]=0;
scanf("%d%d%s",&n,&k,str);
for(i=0;i<n;i++)
b[str[i]-'a'][++b[str[i]-'a'][0]]=i;
for(i=0;i<=n;i++)
for(j=0;j<26;j++)
if(solve2(i-1,i)+1>=solve1(0,n-1)+k || !k)
ans++;
else
for(l=1;l<=b[j][0];l++)
if((b[j][l]<i && solve1(b[j][l]+1,i-1)+solve2(b[j][l]-1,i)+2>=solve1(0,n-1)+k) || (b[j][l]>=i && solve1(i,b[j][l]-1)+solve2(i-1,b[j][l]+1)+2>=solve1(0,n-1)+k)){
ans++;
break;
}
printf("%d\n",ans);
}
return 0;
}
int max(int x,int y){
return (x>y)?x:y;
}
int solve1(int x,int y){
if(x>y)
return 0;
if(x==y)
return 1;
if(dp1[x][y]!=-1)
return dp1[x][y];
if(str[x]==str[y])
dp1[x][y]=solve1(x+1,y-1)+2;
else
dp1[x][y]=max(solve1(x+1,y),solve1(x,y-1));
return dp1[x][y];
}
int solve2(int x,int y){
if(x>=y || x<0 || y>=n)
return 0;
if(dp2[x][y]!=-1)
return dp2[x][y];
if(str[x]==str[y])
dp2[x][y]=solve2(x-1,y+1)+2;
else
dp2[x][y]=max(solve2(x-1,y),solve2(x,y+1));
return dp2[x][y];
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below