Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Longest Palindromic Subsequence

Yashwant Parihar, August 6, 2023August 1, 2024

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 CcppCSharpHackerrank Solutionsjava

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes