In this HackerRank Longest Palindromic Subsequence problem solution we have Given Q queries consisting of n, k, and s, print the number of different ways of inserting exactly 1 new lowercase letter into string S such that the length of the longest palindromic subsequence of S increases by at least K.

## Problem solution in Java.

```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;
}

}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#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;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#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;
}
```

{"mode":"full","isActive":false}