HackerRank Longest Palindromic Subsequence

Yashwant Parihar,

In this post, we will solve HackerRank Longest Palindromic Subsequence Problem Solution.

Steve loves playing with palindromes. He has a string, s, consisting of n lowercase English alphabetic characters (i.e., a through z). He wants to calculate the number of ways to insert exactly 1 lowercase character into string s such that the length of the longest palindromic subsequence of $ increases by at least k. Two ways are considered to be different if either of the following conditions are satisfied:

  • The positions of insertion are different.
  • The inserted characters are different.

This means there are at most 26 x (n + 1) different ways to insert exactly 1 character into
a string of length n.
Given q queries consisting of n. k, and s. print the number of different ways of inserting exactly 1 new lowercase letter into string & such that the length of the longest palindromic subsequence of S increases by at least k.
Input Format
The first line contains a single integer, q, denoting the number of queries. The 2q subsequent lines describe each query over two lines:

  1. The first line of a query contains two space-separated integers denoting the respective values of n and k.
  2. The second line contains a single string denoting s.

Output Format
On a new line for each query, print the number of ways to insert exactly 1 new lowercase letter into strings such that the length of the longest palindromic subsequence of s increases by at least k.

Sample Input

3
1 1
a
3 2
aab
3 0
aba

Sample Output

2
1
104

Explanation
We perform the following q = 2 queries:

  1. The length of the longest palindromic subsequence of s = a is 1. There are two ways to increase this string’s length by at least k = 1:
  2. Insert an a at the start of string s. making it aa.
  3. Insert an a at the end of strings, making it aa.
    Both methods result in aa, which has a longest palindromic subsequence of length 2 (which is longer than the original longest palindromic subsequence’s length by k = 1). Because there are two such ways, we print 2 on a new line.
  4. The length of the longest palindromic subsequence of s = aab is 2. There is one way to increase the length by at least k = 2:
  5. Insert a b at the start of string s, making it baab.
    We only have one possible string, baab, and the length of its longest palindromic subsequence is 4 (which is longer than the original longest palindromic subsequence’s length by k = 2). Because there is one such way, we print 1 on a new line.
HackerRank Longest Palindromic Subsequence Problem Solution
HackerRank Longest Palindromic Subsequence Problem Solution

Longest Palindromic Subsequence C Solution

#include<stdio.h>
#define M 3005
int q, n, k;
char s[M];
int in[M][M], out[M][M];
int max(int a, int b)
{
    return a > b ? a : b;
}
int main()
{
    scanf("%d", &q);
    while(q--)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", s);
        if( k == 0 )
        {
            printf("%d\n", ( n + 1 ) * 26);
            continue;
        }
        if( k > 2 )
        {
            printf("0\n");
            continue;
        }
        for( int l = 0 ; l < n ; l++ )
        {
            for( int i = 0 ; i + l < n ; i++ )
            {
                int j = i + l;
                if( i == j )
                {
                    in[i][j] = 1;
                }
                else if( s[i] == s[j] )
                {
                    if( i + 1 < j )
                    {
                        in[i][j] = 2 + in[i+1][j-1];
                    }
                    else
                    {
                        in[i][j] = 2;
                    }
                }
                else
                {
                    in[i][j] = max(in[i+1][j], in[i][j-1]);
                }
            }
        }
        for( int l = n - 1 ; l >= 0 ; l-- )
        {
            for( int i = 0 ; i + l < n ; i++ )
            {
                int j = i + l;
                if( i == j )
                {
                    if( 0 < i && j + 1 < n )
                    {
                        out[i][j] = 1 + out[i-1][j+1];
                    }
                    else
                    {
                        out[i][j] = 1;
                    }
                }
                else if( s[i] == s[j] )
                {
                    if( 0 < i && j + 1 < n )
                    {
                        out[i][j] = 2 + out[i-1][j+1];
                    }
                    else
                    {
                        out[i][j] = 2;
                    }
                }
                else
                {
                    out[i][j] = 0;
                    if( 0 < i )
                    {
                        out[i][j] = max(out[i][j], out[i-1][j]);
                    }
                    if( j + 1 < n )
                    {
                        out[i][j] = max(out[i][j], out[i][j+1]);
                    }
                }
            }
        }
        int cur = in[0][n-1], res = 0;
        for( int i = 0 ; i <= n ; i++ )
        {
            for( char ch = 'a' ; ch <= 'z' ; ch++ )
            {
                int my = ( i == 0 || i == n ) ? 1 : 1 + out[i-1][i];
                for( int j = 0 ; j < i && my < cur + k ; j++ )
                {
                    if( s[j] == ch )
                    {
                        int cand = 2;
                        if( 0 < j && i < n )
                        {
                            cand += out[j-1][i];
                        }
                        if( j + 1 <= i - 1 )
                        {
                            cand += in[j+1][i-1];
                        }
                        my = max(my, cand);
                    }
                }
                for( int j = i ; j < n && my < cur + k ; j++ )
                {
                    if( s[j] == ch )
                    {
                        int cand = 2;
                        if( 0 < i && j + 1 < n )
                        {
                            cand += out[i-1][j+1];
                        }
                        if( i <= j - 1 )
                        {
                            cand += in[i][j-1];
                        }
                        my = max(my, cand);
                    }
                }
                if( my >= cur + k )
                {
                    res++;
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Longest Palindromic Subsequence C++ 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;
}

Longest Palindromic Subsequence C Sharp Solution

using System.IO;
using System.Linq;
//using System.Text;
using System;

class Solution {


  static int[,] Lcs(char[] arr,char[] b){
        int[,] lcs = new int[arr.Count()+1,b.Count()+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;
    }
    
     static int[,] CalcLPS(char[] arr){
        int[,] lps = new int[arr.Count(),arr.Count()];
        int i,j,k;
        for(i=0;i<arr.Length;i++){
            lps[i,i] = 1;
        }
        
        for(k=2;k<=arr.Length;k++){
            for(i=0;i<=arr.Length-k;i++){
                j = i+k-1;
                if(j==i+1){
                   
                    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;
    }
    
      static int CalcWays(int[,] lps,int[,] lcs,char[] arr,int lp){
        int n = arr.Length;
        int i,j,k;
        int ans = 0;
       
        int[] table = new int[26];
        
        for(i=0;i<=arr.Length;i++){
            
            int x = Math.Max(lps[0,n-1], 1+lcs[i,n-i]*2);
            for(k=0;k<=25;k++){
                table[k] = x;
            }       
                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;
    }
    
    private static char[] ReverseCharArray(char[] arr){
        char[] rev = new char[arr.Count()];
        int i,n= arr.Count()-1;
        for(i=0;i<=n;i++){
            rev[i] = arr[n-i];
        }
        return rev;
    }
    
    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int q = Convert.ToInt32(Console.ReadLine());

        for (int qItr = 0; qItr < q; qItr++) {
            string[] nk = Console.ReadLine().Split(' ');

            int n = Convert.ToInt32(nk[0]);

            int k = Convert.ToInt32(nk[1]);

            string s = Console.ReadLine();
            var arr = s.ToCharArray();

            if(k == 0){
                 textWriter.WriteLine((26*(n+1)));
                //Console.WriteLine(26*(n+1));
            }
            else if(n == 1){
                 textWriter.WriteLine(2);
                //Console.WriteLine(2);
            }
            else{
                int[,] lps = CalcLPS(arr);
                int[,] lcs = Lcs(arr, ReverseCharArray(arr));
                int ans = CalcWays(lps,lcs,arr,k);
               // Console.WriteLine(ans);
                textWriter.WriteLine(ans);
            }
        }

        textWriter.Flush();
        textWriter.Close();
    }
    
   
}

Longest Palindromic Subsequence Java Solution

import java.io.*;
import java.util.*;

public class Solution {
    static int N;
    static int K;
    static String S;
    
    static int[][] dp;
    static int[][] dpX;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        dp = new int[3002][3002];
        dpX = new int[3002][3002];

        int T = in.nextInt();
        for(int i = 0; i < T; i ++) {
            N = in.nextInt();
            K = in.nextInt();
            S = in.next("[a-z]+");
            int result = solve();
            System.out.println(result);
        }
    }

    static int solve() {
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
            Arrays.fill(dpX[i], -1);
        }

        int result;
        if (K == 0) {
            result = 26 * (N + 1);
        } else {
            result = 0;
            for (int i = 0; i <= N; i++) {
                int countOfExtend = countOfExtend(i);
                result += countOfExtend;
            }
            return result;
        }
        return result;
    }

    private static int countOfExtend(int at) {
        int base = count(0, N);
        if (at > 0 && at < N) {
            if (countOuter(at, at + 1) + 1 - base >= K) {
                return 26;
            }
        }
        boolean[] usedChars = new boolean[26];
        int result = 0;
        for (int i = 0; i < N; i++) {
            int ch = S.charAt(i) - 'a';
            if (!usedChars[ch]) {
                int from = Math.min(i, at);
                int to = Math.max(i, at);
                int outer;
                int inner;
                if (i < at) {
                    outer = countOuter(from - 1, to);
                    inner = count(from + 1, to);
                }
                else {
                    outer = countOuter(from - 1, to + 1);
                    inner = count(from, to);
                }
                if (inner < 0 || outer < 0) {
                    throw new IllegalStateException();
                }

                if (outer + inner + 2 - base >= K) {
                    usedChars[ch] = true;
                    result ++;
                }
            }
        }

        return result;
    }

    static int countOuter(int from, int to) {
        if (from == -1 || to >= N) {
            return 0;
        }
        else {
            int result = dpX[from][to];
            if (result >= 0) {
                return result;
            }
            int a = S.charAt(from);
            int b = S.charAt(to);
            if (a == b) {
                result = countOuter(from - 1, to + 1) + 2;
            }
            else {
                result = Math.max(countOuter(from - 1, to), countOuter(from, to + 1));
            }

            dpX[from][to] = result;
            return result;
        }
    }


    static int count(int from, int to) {
        if (from == to) {
            return 0;
        }
        else if (from + 1 == to) {
            return 1;
        }

        int result = dp[from][to];
        if (result >= 0) {
            return result;
        }

        int a = S.charAt(from);
        int b = S.charAt(to - 1);

        if (a == b) {
            result = count(from + 1, to - 1) + 2;
        }
        else {
            result = Math.max(count(from + 1, to), count(from, to - 1));
        }

        dp[from][to] = result;
        return result;
    }

    
}
c C# C++ HackerRank Solutions java