Shashank and the Palindromic Strings – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Shashank and the Palindromic Strings HackerRank Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i < int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define x first
#define y second
template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));
mt19937 mt(time(NULL));
const int N = 1000 + 13;
int n;
string s[N];
char buf[N];
inline void gen()
{
n = 50;
forn (i, n)
{
s[i].resize(20);
forn (j, 20)
s[i][j] = char(mt() % 2 + 'a');
}
}
inline bool read()
{
//gen();
//return true;
if (scanf ("%d", &n) != 1)
return false;
forn (i, n)
{
assert(scanf ("%s", buf) == 1);
s[i] = string(buf);
}
return true;
}
const int MOD = 1000 * 1000 * 1000 + 7;
inline int norm (int val)
{
if (val >= MOD)
val -= MOD;
return val;
}
int m;
int poss[N];
char t[N];
int d[N][N][2][2][2];
inline void solve()
{
m = 0;
forn (i, n)
forn (j, sz(s[i]))
{
t[m] = s[i][j];
poss[m++] = i;
}
memset(d, 0, sizeof d);
d[0][m - 1][0][0][0] = 1;
int ans = 0;
forn (i, m)
for(int j = m - 1; j >= i; j--)
forn(k, 2)
forn (c1, 2)
forn (c2, 2)
{
int dv = d[i][j][k][c1][c2];
if (!dv)
continue;
if (i == j)
{
//cerr << 'B' << ' ' << i << ' ' << j << ' ' << k << ' ' << c1 << ' ' << c2 << ' ' << dv << endl;
ans = norm(ans + dv);
continue;
}
if (k == 0)
{
d[i][j][1][c1][c2] = norm(d[i][j][1][c1][c2] + dv);
if (poss[i + 1] == poss[i] || c1)
{
int nc1 = c1;
if (poss[i + 1] != poss[i])
nc1 = 0;
d[i + 1][j][0][nc1][c2] = norm(d[i + 1][j][0][nc1][c2] + dv);
}
}
else
{
if (poss[j - 1] == poss[j] || c2)
{
int nc2 = c2;
if (poss[j - 1] != poss[j])
nc2 = 0;
d[i][j - 1][1][c1][nc2] = norm(d[i][j - 1][1][c1][nc2] + dv);
}
if (t[i] == t[j])
{
int nc1, nc2;
if (poss[i + 1] != poss[i])
nc1 = 0;
else
nc1 = 1;
if (poss[j - 1] != poss[j])
nc2 = 0;
else
nc2 = 1;
if (i + 1 == j)
{
//cerr << 'C' << ' ' << i << ' ' << j << ' ' << k << ' ' << c1 << ' ' << c2 << ' ' << dv << endl;
ans = norm(ans + dv);
}
else
{
if (poss[i] == poss[j] || poss[i] + 1 == poss[j])
{
//cerr << 'A' << ' ' << i << ' ' << j << ' ' << k << ' ' << c1 << ' ' << c2 << ' ' << dv << endl;
ans = norm(ans + dv);
}
d[i + 1][j - 1][0][nc1][nc2] = norm(d[i + 1][j - 1][0][nc1][nc2] + dv);
}
}
}
}
cout << ans << endl;
}
int main()
{
#ifdef SU2_PROJ
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
cout << setprecision(25) << fixed;
cerr << setprecision(10) << fixed;
srand(int(time(NULL)));
int testCnt;
assert(scanf ("%d", &testCnt) == 1);
forn (test, testCnt)
{
assert(read());
solve();
}
#ifdef SU2_PROJ
cerr << "TIME: " << clock() << endl;
#endif
return 0;
}
Java Shashank and the Palindromic Strings HackerRank Solution
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class ShashankAndThePalindromicStrings {
private static final int MOD = 1000000000 + 7;
private static class L1Tree {
private static final int MAX_SIZE = 2 * 1024;
private L2Tree[] l2Trees = new L2Tree[MAX_SIZE];
private int maxX;
private L1Tree() {
IntStream.range(0, MAX_SIZE).forEach(i -> l2Trees[i] = new L2Tree());
}
private void init(int maxX1, int maxX2) {
maxX = maxX1;
Arrays.stream(l2Trees).forEach(t -> t.init(maxX2));
}
private void put(int x1, int x2, int val) {
int idx = 0;
int l = 0;
int r = maxX;
while (r - l > 0) {
l2Trees[idx].put(x2, val);
int mid = (r + l) / 2;
if (x1 <= mid) {
idx = 2 * idx + 1;
r = mid;
} else {
idx = 2 * idx + 2;
l = mid + 1;
}
}
l2Trees[idx].put(x2, val);
}
private int getSum(int fromX1, int toX1, int fromX2, int toX2) {
if (fromX1 > toX1 || fromX2 > toX2) return 0;
return _getSum(0, maxX, 0, fromX1, toX1, fromX2, toX2);
}
private int _getSum(int l, int r, int idx, int fromX1, int toX1, int fromX2, int toX2) {
if (l > r) return 0;
if (fromX1 <= l && r <= toX1) { // contains
return l2Trees[idx].getSum(fromX2, toX2);
} else if (!(fromX1 > r || l > toX1)) { // intersects
return (_getSum(l, (l + r) / 2, 2 * idx + 1, fromX1, toX1, fromX2, toX2) + _getSum((l + r) / 2 + 1, r, 2 * idx + 2, fromX1, toX1, fromX2, toX2)) % MOD;
} else {
return 0;
}
}
}
private static class L2Tree {
private static final int MAX_SIZE = 2 * 1024;
private int sum[] = new int[MAX_SIZE];
private int maxX;
private void init(int maxX) {
this.maxX = maxX;
Arrays.fill(sum, 0);
}
private void put(int x, int val) {
int idx = 0;
int l = 0;
int r = maxX;
while (r - l > 0) {
sum[idx] = (sum[idx] + val) % MOD;
int mid = (r + l) / 2;
if (x <= mid) {
idx = 2 * idx + 1;
r = mid;
} else {
idx = 2 * idx + 2;
l = mid + 1;
}
}
sum[idx] = (sum[idx] + val) % MOD;
}
private int getSum(int fromX, int toX) {
return _getSum(0, maxX, 0, fromX, toX);
}
private int _getSum(int l, int r, int idx, int fromX, int toX) {
if (l > r) return 0;
if (fromX <= l && r <= toX) { // contains
return sum[idx];
} else if (!(fromX > r || l > toX)) { // intersects
return (_getSum(l, (l + r) / 2, 2 * idx + 1, fromX, toX) + _getSum((l + r) / 2 + 1, r, 2 * idx + 2, fromX, toX)) % MOD;
} else {
return 0;
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
L1Tree tree = new L1Tree();
IntStream.range(0, in.nextInt()).forEach(t -> {
int n = in.nextInt();
String[] a = IntStream.range(0, n).mapToObj(i -> in.next()).toArray(String[]::new);
String total = Arrays.stream(a).collect(Collectors.joining());
int totalLength = total.length();
int[] groupIdx = new int[totalLength];
int[] groupStartIdx = new int[n];
int[] groupEndIdx = new int[n];
int tmp = 0;
for (int i = 0; i < n; i++) {
Arrays.fill(groupIdx, tmp, tmp + a[i].length(), i);
groupStartIdx[i] = tmp;
groupEndIdx[i] = tmp + a[i].length() - 1;
tmp += a[i].length();
}
tree.init(totalLength - 1, totalLength - 1);
for (int d = 0; d < totalLength; d++) {
for (int b = 0, e = b + d; e < totalLength; b++, e++) {
if (total.charAt(b) != total.charAt(e)) continue;
int cnt = 0;
if (groupIdx[e] - groupIdx[b] <= 1) cnt = 1;
cnt += tree.getSum(
b + 1,
groupEndIdx[Math.min(groupIdx[b] + 1, n - 1)],
groupStartIdx[Math.max(0, groupIdx[e] - 1)],
e - 1
);
tree.put(b, e, cnt);
}
}
System.out.println(tree.getSum(groupStartIdx[0], groupEndIdx[0], groupStartIdx[n - 1], groupEndIdx[n - 1]));
});
}
}
C Shashank and the Palindromic Strings HackerRank 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);
}
//printf("%d %d %d %d %u\n", i, j, oi, oj, c % md);
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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
