HackerRank Shashank and the Palindromic Strings Yashwant Parihar, August 2, 2023August 1, 2024 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-emptysubsequences 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 FormatThe 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 abc Sample Output 0 5 0 9 Explanation 0The 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. HackerRank Shashank and the Palindromic Strings Problem Solution 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(); } } c C# C++ HackerRank Solutions java CcppCSharpHackerrank Solutionsjava