# HackerRank Shashank and the Palindromic Strings problem solution

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.

## 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];
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++) {
if (!edge[i] && (mask & 3) == 3) {
continue;
}
ans = (ans + a[i][mask]) % MOD;
}
}
return ans;
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int q = Integer.parseInt(st.nextToken());

for (int i = 0; i < q; i++) {
int m = Integer.parseInt(st.nextToken());

char[][] parts = new char[m][];
int n = 0;
for (int j = 0; j < m; j++) {
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;

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;
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("%u\n", 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}