In this post, we will solve HackerRank Shashank and the Palindromic Strings Problem Solution.
Shashank loves strings, but he loves palindromic strings the most. He has a list of n strings.
A = [ao, a1,…, an-1]. where each string, a,, consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty
subsequences 80, 81, 82, …, 8-1 such that the following conditions are satisfied:
1.80 is a subsequence of string ap. 81 is a subsequence of string a1, 82 is a subsequence of string a2….. and 8-1 is a subsequence of string an-1.
2.80 +81 +82 + … + 8-1 is a palindromic string, where + denotes the string concatenation operator.
You are 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 109 +7, on a new line.
Note: Two subsequences consisting of the same characters are considered to be different if their characters came from different indices in the original string.
Input Format
The first line contains a single integer. q. denoting the number of queries. The subsequent lines describe each query in the following format:
- The first line contains an integer, n. denoting the size of the list.
- Each line i of the n subsequent lines contains a non-empty string describing a,.
Sample Input 0
3
3
aa
b
aa
3
a
b
c
2
abc
abcSample Output 0
5
0
9Explanation 0
The first two queries are explained below:
- We can choose the following five subsequences:
1.50 “a”. 81=”b”, sâ‚‚ = “a”, where so is the first character of ap and 82 is the first character of a2.
2.80= “a”, 81 = “b”, 82=”a”, where so is the second character of a and 82 is the second character of a2.
3.50″a”. 81 “b”, 82 = second character of a2. = “a”, where so is the first character of ap and 82 is the - 50 “a”, 81 = “b”, 82 the first character of a2. = “a”, where 80 is the second character of a, and 82 is
- So “aa”, s = “b”, 82 = “aa”
Thus, we print the result of 5 mod (109 +7)= 5 on a new line. - There is no way to choose non-empty subsequences such that their concatenation results in a palindrome, as each string contains unique characters. Thus, we print 0 on a new line.
Shashank and the Palindromic Strings C Solution
#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("%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;
}Shashank and the Palindromic Strings C++ Solution
#include <algorithm>
#include <cstring>
#include <iostream>
#include <type_traits>
#include <utility>
using namespace std;
#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ROF(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (b); --i >= (a); )
const long L = 1000, MOD = 1000000007;
char a[L+1], b[L+1];
long s[L][L][2][2], p[L][L][2][2], d[L];
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
long cases, n, m;
for (cin >> cases; cases--; ) {
cin >> n;
fill_n(b, L+1, 0);
m = 0;
REP(i, n) {
cin >> a+m;
b[m] = 1;
m += strlen(a+m);
}
REP(i, m)
b[i+1] += b[i];
memset(s, 0, sizeof s);
memset(p, 0, sizeof s);
REP(i, m)
REP(x, 2)
REP(y, 2)
s[i][i][x][y] = 1;
ROF(i, 0, m) {
FOR(j, i+1, m)
REP(x, 2)
REP(y, 2) {
long l = b[i+1]-b[i],
// do not take i
c = ! x && l ? 0 : s[i+1][j][l ? b[i+1] == b[j] ? y : 0 : x][y];
// single i
if (b[j]-b[i] <= y)
c++;
// pair (i, k+1)
c += p[i+1][j][x][y];
s[i][j][x][y] = c%MOD;
}
if (i)
REP(x, 2)
REP(y, 2) {
long ps = 0, t = y, jj = i-1, c;
FOR(j, i, m) {
c = 0;
if (a[i-1] == a[j]) {
long x1 = 1-(b[i]-b[i-1]), y1 = 1-(b[j]-b[j-1]);
if (b[i] == b[j-1])
x1 = y1 = 1;
c += s[i][j-1][x1][y1];
if (b[j]-b[i-1] <= 1)
c++;
}
ps += d[j] = c%MOD;
if (b[j]-b[j-1] && --t < 0)
for(;;) {
if (i <= jj)
ps -= d[jj];
jj++;
if (b[jj]-b[jj-1]) {
t++;
break;
}
}
p[i][j][x][y] = ps%MOD;
}
}
}
cout << s[0][m-1][0][0] << '\n';
}
}Shashank and the Palindromic Strings C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static bool DEBUG = false;
const int MODULO = 1000000007;
string S;
int Len;
int[] Start; // Start index of this string
int[] End; // End index of this string
int[] sIndex; // Index of this letter's string
int[] Prev; // Last letter of previous string
int[] Next; // First letter of next string
long[,] DP; // [i,j] = CPS of the substring from i to j (from the whole constructed string)
static void Main(String[] args) {
int T = Convert.ToInt32(Console.ReadLine());
for (int t = 0; t < T; t++) {
int N = Convert.ToInt32(Console.ReadLine());
int N2 = N + 2;
string[] A = new string[N];
string[] A2 = new string[N2]; // Add extra "a" onto beginning and end to avoid edge cases
A2[0] = "a";
for (int n = 0; n < N; n++) {
A[n] = Console.ReadLine();
A2[n+1] = A[n];
}
A2[N2-1] = "a";
//Solution soln = new Solution(N, A);
//long result = soln.Solve(N, A, MODULO);
Solution soln = new Solution(N2, A2);
long result = soln.Solve(N2, A2, MODULO);
Console.WriteLine(result);
}
}
public Solution(int N, string[] A) {
S = "";
Start = new int[N];
End = new int[N];
int length = 0;
for (int n = 0; n < N; n++) {
S += A[n];
Start[n] = length;
length += A[n].Length;
End[n] = length-1;
}
Len = length;
DP = new long[Len, Len];
sIndex = new int[Len];
Prev = new int[Len];
Next = new int[Len];
for (int n = 0; n < N; n++) {
for (int i = 0; i < A[n].Length; i++) {
sIndex[Start[n]+i] = n;
if (n > 0)
Prev[Start[n]+i] = End[n-1];
if (n < N-1)
Next[Start[n]+i] = Start[n+1];
}
}
}
long Solve(int N, string[] A, int mod) {
if (DEBUG) {
Console.WriteLine("A = " + ArrayToString(A));
Console.WriteLine("S = {0}, Len = {1}", S, Len);
Console.WriteLine("Start = " + ArrayToString(Start));
Console.WriteLine("End = " + ArrayToString(End));
Console.WriteLine("sIndex = " + ArrayToString(sIndex));
Console.WriteLine("Prev = " + ArrayToString(Prev));
Console.WriteLine("Next = " + ArrayToString(Next));
}
return CPS(A, mod);
}
long CPS(string[] A, int mod) {
for (int i = 0; i < Len; i++)
DP[i, i] = 1;
for (int len = 2; len <= Len; len++) {
for (int i = 0; i <= Len-len; i++) {
// Num palindromes, starting at i (or later, but in same string) and ending at j (or before, but in same string)
int j = i + len - 1;
int state = 0;
if (sIndex[i] == sIndex[i+1]) { // If i+1 letter is part of i string then add
DP[i, j] = Mod(DP[i, j] + DP[i+1, j], mod);
state += 1;
}
if (sIndex[j] == sIndex[j-1]) { // If j-1 letter is part of j string then add
DP[i, j] = Mod(DP[i, j] + DP[i, j-1], mod);
state += 2;
}
if (state == 3) // If both states above occurred then subtract the duplicate amount
DP [i, j] = Mod(DP[i, j] - DP[i+1, j-1],mod);
if (S[i] == S[j]) { // If the letters are the same add the extra palindromes
DP[i, j] = Mod(DP[i, j] + DP[i+1, j-1], mod);
state = 0;
if (Next[i] != i+1) { // If we're not at the end of i string
DP[i, j] = Mod(DP[i, j] + DP[Next[i], j-1], mod);
state += 1;
}
if (Prev[j] != j-1) { // If we're not at the start of j string
DP[i, j] = Mod(DP[i, j] + DP[i+1, Prev[j]], mod);
state += 2;
}
if (state == 3) // If both states above occurred then add the next strings as well
DP[i, j] = Mod(DP[i, j] + DP[Next[i], Prev[j]], mod);
if (sIndex[i]+1 == sIndex[j] || sIndex[i] == sIndex[j]) // If i and j are in the middle or middle two strings
DP[i, j] = Mod(DP[i, j] + 1, mod);
}
}
}
long result = DP[0, Len-1];
return result;
}
// Returns the total number of palindromic subsequences for a single string s
long CountPS(int start, string s, int mod) {
int N = s.Length;
//long[,] DP = new long[N, N]; // [i, j] = CPS of substring starting at i and ending at j
for (int i = start; i < start+N; i++) // Single letters are all palindromes
DP[i, i] = 1;
for (int len = 2; len <= N; len++) { // Check all substrings of length len
for (int i = start; i <= start+N-len; i++) {
int j = i + len - 1;
if (S[i] == S[j])
DP[i, j] = (DP[i, j-1] + DP[i+1, j] + 1) % mod;
else
DP[i, j] = (DP[i, j-1] + DP[i+1, j] - DP[i+1, j-1]) % mod;
}
}
if (DEBUG) {
Console.WriteLine("DP:");
PrintDP(S, DP);
}
return DP[start, start+N-1];
}
// Returns the total number of palindromic subsequences between 2 strings
long CountPS(int start, string s1, string s2, int mod) {
int N1 = s1.Length;
int N2 = s2.Length;
string s = s1 + s2;
int N = N1 + N2;
if (DEBUG) Console.WriteLine("s={0}", s);
long[,] DP1 = new long[N, N]; // [i, j] = CPS of substring starting at i and ending at j
for (int i = 0; i < N; i++) // Single letters are all palindromes
DP1[i, i] = 1;
for (int len = 2; len <= N; len++) { // Check all substrings of length len (must be 2 and above)
for (int i = 0; i <= N-len; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] - DP1[i+1, j-1] + DP1[i+1, j-1] + 1) % mod;
if (i < N1 && j >= N1) // If i is part of s1 and j is part of s2, then valid substring
DP[start+i, start+j] = (DP[start+i, start+j-1]
+ DP[start+i+1, start+j]
- DP[start+i+1, start+j-1]
+ DP1[i+1, j-1] + 1) % mod;
} else {
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] - DP1[i+1, j-1]) % mod;
if (i < N1 && j >= N1) // If i is part of s1 and j is part of s2, then valid substring
DP[start+i, start+j] = (DP[start+i, start+j-1]
+ DP[start+i+1, start+j]
- DP[start+i+1, start+j-1]) % mod;
}
}
}
if (DEBUG) {
Console.WriteLine("DP1:");
PrintDP(s, DP1);
Console.WriteLine("DP:");
PrintDP(S, DP);
}
return DP[start, start+N-1];
}
// Returns the total number of palindromic subsequences between 3 strings
long CountPS(int start, string s1, string m, string s2, int mod) {
int N1 = s1.Length;
int Nm = m.Length;
int N2 = s2.Length;
string s = s1 + m + s2;
int N = N1 + Nm + N2;
if (DEBUG) Console.WriteLine("s={0}", s);
long[,] DP1 = new long[N, N]; // Using single string
for (int i = 0; i < N; i++) {
if (i >= N1 && i < N1+Nm) // Copy from DP
DP1[i, i] = DP[i, i];
else // Else single letters are palindrome
DP1[i, i] = 1;
}
long[,] DP2 = new long[N, N]; // Using 2 strings
for (int len = 2; len <= N; len++) { // Check all substrings of length len (must be 2 and above)
for (int i = 0; i <= N-len; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
if (i >= N1 && i < N1+Nm && j >= N1 && j < N1+Nm) { // Inside middle string, copy from DP
DP1[i, j] = DP[start+i, start+j];
} else if (i < N1 && j >= N1+Nm) { // Inside valid range (i within s1, j within s2)
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] + 1) % mod;
DP2[i, j] = (DP2[i, j-1] + DP2[i+1, j] - DP2[i+1, j-1] + DP1[i+1, j-1] + 1) % mod;
if (i == N1-1 && j == N1+Nm)
DP[start+i, start+j] = 0;
else
DP[start+i, start+j] = (DP[start+i, start+j-1]
+ DP[start+i+1, start+j]
- DP[start+i+1, start+j-1]
+ DP2[i+1, j-1] + 1) % mod;
} else { // Inside range using only 2 strings (middle and one of s1 or s2)
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] + 1) % mod;
DP2[i, j] = (DP2[i, j-1] + DP2[i+1, j] - DP2[i+1, j-1] + DP1[i+1, j-1] + 1) % mod;
}
} else {
if (i >= N1 && i < N1+Nm && j >= N1 && j < N1+Nm) { // Inside middle string, copy from DP
DP1[i, j] = DP[start+i, start+j];
} else if (i < N1 && j >= N1+Nm) { // Inside valid range (i within s1, j within s2)
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] - DP1[i+1, j-1]) % mod;
DP2[i, j] = (DP2[i, j-1] + DP2[i+1, j] - DP2[i+1, j-1]) % mod;
if (i == N1-1 && j == N1+Nm)
DP[start+i, start+j] = 0;
else
DP[start+i, start+j] = (DP[start+i, start+j-1]
+ DP[start+i+1, start+j]
- DP[start+i+1, start+j-1]) % mod;
} else { // Inside range using only 2 strings (middle and one of s1 or s2)
DP1[i, j] = (DP1[i, j-1] + DP1[i+1, j] - DP1[i+1, j-1]) % mod;
DP2[i, j] = (DP2[i, j-1] + DP2[i+1, j] - DP2[i+1, j-1]) % mod;
}
}
}
}
if (DEBUG) {
Console.WriteLine("DP1:");
PrintDP(s, DP1);
Console.WriteLine("DP2:");
PrintDP(s, DP2);
Console.WriteLine("DP:");
PrintDP(S, DP);
}
return DP[start, start+N-1];
}
long Mod(long x, int mod) {
return (x % mod + mod) % mod;
}
string ArrayToString<T>(IEnumerable<T> collection) {
return "[" + string.Join(",", collection) + "]";
}
void PrintMatrix(int[,] M) {
int I = M.GetLength(0);
int J = M.GetLength(1);
for (int i = 0; i < I; i++) {
for (int j = 0; j < J-1; j++)
Console.Write("{0},", M[i, j]);
if (J > 0)
Console.Write("{0}", M[i, J-1]);
Console.WriteLine();
}
}
void PrintDP(string s, long[,] M) {
int I = M.GetLength(0);
int J = M.GetLength(1);
Console.Write(" ");
for (int i = 0; i < I; i++)
Console.Write(" {0}", s[i]);
Console.WriteLine();
for (int i = 0; i < I; i++) {
Console.Write("{0}|", s[i]);
for (int j = 0; j < J-1; j++)
Console.Write("{0},", M[i, j]);
if (J > 0)
Console.Write("{0}", M[i, J-1]);
Console.WriteLine();
}
}
}Shashank and the Palindromic Strings Java Solution
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();
}
}
