HackerRank Longest Palindromic Subsequence problem solution YASH PAL, 31 July 2024 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. Topics we are covering Toggle Problem solution in Java.Problem solution in C++.Problem solution in C. 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("%dn",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("%dn",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("%dn", ( n + 1 ) * 26); continue; } if( k > 2 ) { printf("0n"); 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("%dn", res); } return 0; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions