HackerRank Shashank and the Palindromic Strings
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();
}
}
