HackerRank Shashank and the Palindromic Strings problem solution YASH PAL, 31 July 2024 In this HackerRank Shashank and the Palindromic Strings problem solution, we have given Q queries where each query consists of some list, A. For each query, find and print the number of ways Shashank can choose N non-empty subsequences satisfying the criteria above, modulo 10 to power 9 plus 7, on a new line. 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 final int A = 26 * 4; static final int MASKS = A + 4; static final int MOD = 1_000_000_007; static int solve(char[][] parts, int n) { int m = parts.length; int[] s = new int[n]; boolean[] edge = new boolean[n + 1]; edge[0] = true; for (int i = 0, j = 0; i < m; i++) { for (int k = 0; k < parts[i].length; k++) { s[j++] = (parts[i][k] - 'a') << 2; } edge[j] = true; } int[][] a = new int[n + 1][MASKS]; int[][] b = new int[n + 1][MASKS]; a[0][A + 3] = 1; for (int len = n; len > 0; len--) { Arrays.fill(b[0], 0); for (int i = 0; i <= n - len; i++) { int j = i + len; int leftNext = edge[i + 1] ? 2 : 0; int rightNext = edge[j - 1] ? 1 : 0; int[] ai = a[i]; int[] bi = b[i]; int[] bi1 = b[i + 1]; Arrays.fill(bi1, 0); int si = s[i]; int sj = s[j - 1]; for (int mask = 0; mask < MASKS; mask++) { int value = ai[mask]; if (value == 0) { continue; } int letter = mask & ~3; int left = mask & 2; int right = mask & 1; int index; if (letter == A) { index = si | leftNext | right; bi1[index] = (bi1[index] + value) % MOD; if ((leftNext & left) == 0) { index = A | leftNext | left | right; bi1[index] = (bi1[index] + value) % MOD; } } else { if (sj == letter) { index = A | left | rightNext; bi[index] = (bi[index] + value) % MOD; } if ((rightNext & right) == 0) { index = letter | left | rightNext | right; bi[index] = (bi[index] + value) % MOD; } } } } int[][] temp = a; a = b; b = temp; } int ans = 0; for (int i = 0; i <= n; i++) { for (int mask = 0; mask < MASKS; mask++) { if (!edge[i] && (mask & 3) == 3) { continue; } ans = (ans + a[i][mask]) % MOD; } } return ans; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int q = Integer.parseInt(st.nextToken()); for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); char[][] parts = new char[m][]; int n = 0; for (int j = 0; j < m; j++) { parts[j] = br.readLine().toCharArray(); n += parts[j].length; } long result = solve(parts, n); bw.write(String.valueOf(result)); bw.newLine(); } br.close(); bw.close(); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include<cstring> using namespace std; const int MOD=1e9+7; string s[50]; int dp[1001][1001]; int dpsum[1001][1001]; vector<int> len; vector<int> lenSum; void solve(string t,int n){ memset(dp,0,sizeof(dp)); memset(dpsum,0,sizeof(dpsum)); int l=t.size(); for(int k=1;k<=l;k++){ for(int i=0;i+k-1<l;i++){ if(k==1){ dp[i][i]=1; dpsum[i][i]=1; } else{ int j=i+k-1; int thisI=(lower_bound(lenSum.begin(),lenSum.end(),i+1)-lenSum.begin()); int thisJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1)-lenSum.begin()); if(t[i]==t[j]) { dp[i][j]=dpsum[i+1][j-1]; if(thisI==thisJ) dp[i][j]=(dp[i][j]+1)%MOD; else{ if(i+1!=lenSum[thisI])dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][j-1])%MOD; if(j!=lenSum[thisJ-1])dp[i][j]=(dp[i][j]+dpsum[i+1][lenSum[thisJ-1]-1])%MOD; if((i+1!=lenSum[thisI])&&(j!=lenSum[thisJ-1]))dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][lenSum[thisJ-1]-1])%MOD; if(thisI+1==thisJ) dp[i][j]=(dp[i][j]+1)%MOD; } } int nextI=(lower_bound(lenSum.begin(),lenSum.end(),i+1+1)-lenSum.begin()); int prevJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1-1)-lenSum.begin()); if(nextI==thisI && prevJ==thisJ){ dpsum[i][j]=(dpsum[i+1][j]+dpsum[i][j-1])%MOD; dpsum[i][j]=(dpsum[i][j]-dpsum[i+1][j-1])%MOD; dpsum[i][j]=(dpsum[i][j]+dp[i][j])%MOD; } else if(nextI==thisI){ dpsum[i][j]=(dpsum[i+1][j]+dp[i][j])%MOD; } else if(prevJ==thisJ){ dpsum[i][j]=(dpsum[i][j-1]+dp[i][j])%MOD; } else{ dpsum[i][j]=dp[i][j]; } } } } if(dpsum[0][l-1]<0) dpsum[0][l-1]+=MOD; cout<<dpsum[0][l-1]<<endl; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int _test; cin>>_test; while(_test--){ int n; cin>>n; string total=""; len.clear(); lenSum.clear(); lenSum.push_back(0); for(int i=0;i<n;i++){ cin>>s[i]; total.append(s[i]); len.push_back(s[i].size()); lenSum.push_back(lenSum[i]+len[i]); } solve(total,n); } return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define md 1000000007 char cv[1001], fv[1000], lv[1000], gv[1000]; unsigned int mv[1000 * 1000 * 4]; int m; void readInput() { int i, j, k, l, n; char *s; for (i = 0; i < 1000; ++i) { fv[i] = 0; lv[i] = 0; } s = cv; k = 0; scanf("%d", &n); for (i = 0; i < n; ++i) { scanf("%s", s); l = strlen(s); fv[k] = 1; lv[k + l - 1] = 1; for (j = 0; j < l; ++j) { gv[k + j] = i; } k += l; s += l; } m = strlen(cv); } int ix(int i, int j, int oi, int oj) { return (i * m * 4) + (j * 4) + (oi * 2) + oj; } unsigned int f(int i, int j, int oi, int oj) { if (i == j) { return (oi || oj) ? 2 : 1; } if (j < i) { return 1; } if (gv[i] == gv[j]) { oi = oi || oj; oj = oi; } return mv[ix(i, j, oi, oj)]; } void run() { int l, i, j, p; int il, jf, oi, oj, oi1, oj1, b1, b2; unsigned int c; readInput(); for (l = 2; l <= m; ++l) { for (i = 0; i <= m - l; ++i) { j = i + l - 1; for (p = 0; p < 4; ++p) { if (p == 0 || p == 3 || gv[i] < gv[j]) { il = lv[i]; jf = fv[j]; oi = p & 1; oj = p >> 1; c = 0; b1 = oi || !il; b2 = oj || !jf; oi1 = !il && oi; oj1 = !jf && oj; if (b1) { c += f(i + 1, j, oi1, oj); } if (b2) { c += f(i, j - 1, oi, oj1); } if (b1 && b2 && (l > 2 || oi || oj)) { c += md - f(i + 1, j - 1, oi1, oj1); } if (cv[i] == cv[j]) { c += f(i + 1, j - 1, !il, !jf); } mv[ix(i, j, oi, oj)] = c % md; } } } } printf("%un", mv[ix(0, m - 1, 0, 0)]); } int main() { int q, i; scanf("%d", &q); for(i = 0; i < q; ++i) { run(); } return 0; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions