Table of Contents
Circular Palindromes – 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++ Circular Palindromes HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
template<class T> void sort(int N, T a[], void *mem = NULL){sort(a,a+N);}
template<class T1, class T2> void sort(int N, T1 a[], T2 b[], void *mem){int i;pair<T1,T2> *r=(pair<T1, T2>*)mem;rep(i,N)r[i].first=a[i],r[i].second=b[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second;}
template<class T1, class T2, class T3> void sort(int N, T1 a[], T2 b[], T3 c[], void *mem){int i;pair<T1,pair<T2,T3> > *r=(pair<T1,pair<T2,T3> >*)mem;rep(i,N)r[i].first=a[i],r[i].second.first=b[i],r[i].second.second=c[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second.first,c[i]=r[i].second.second;}
template<class T1, class T2, class T3, class T4> void sort(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem){int i;pair<pair<T1,T2>,pair<T3,T4> > *r=(pair<pair<T1,T2>,pair<T3,T4> >*)mem;rep(i,N)r[i].first.first=a[i],r[i].first.second=b[i],r[i].second.first=c[i],r[i].second.second=d[i];sort(r,r+N);rep(i,N)a[i]=r[i].first.first,b[i]=r[i].first.second,c[i]=r[i].second.first,d[i]=r[i].second.second;}
char memarr[77000000]; void *mem = memarr;
#define MD 1000000007
template<class T>
struct rollingHash64{
int len;
T *data;
ull *sum, *rev, *pw;
ull mul;
ull getinv(ull a){
ull t,s=a,u=0,v=1,e;
e = numeric_limits<ull>::max() / s;
t -= e * s;
u -= e * v;
swap(t,s);
swap(u,v);
while(s){
e=t/s;
t-=e*s;
u-=e*v;
swap(t,s);
swap(u,v);
}
return u;
}
void* init(int n, T *arr, ull m = 0, void *mem = NULL){
int i; ull v;
mul = m;
if(mul==0) mul = 2*(rand()%1000000000) + 1000000001ULL;
len = n;
data = arr;
if(mem == NULL){
pw = (ull*)malloc(sizeof(ull)*(2*len+1));
sum = (ull*)malloc(sizeof(ull)*(len+1));
rev = (ull*)malloc(sizeof(ull)*(len+1));
} else {
pw = (ull*)mem;
sum = pw + 2*len + 1;
rev = sum + len + 1;
mem = rev + len + 1;
}
v = getinv(mul);
pw = pw + len;
pw[0] = 1;
rep(i,len) pw[ i+1] = pw[ i] * mul;
rep(i,len) pw[-i-1] = pw[-i] * v;
sum[0] = 0;
rep(i,len) sum[i+1] = sum[i] + (ull)data[i] * pw[i];
rev[len] = 0;
for(i=len-1;i>=0;i--) rev[i] = rev[i+1] + (ull)data[i] * pw[len-i-1];
return mem;
}
ull get(int a, int b, int off=0){
ull res;
if(a <= b){
res = (sum[b+1] - sum[a]) * pw[-a+off] + (b-a+1);
} else {
res = (rev[b] - rev[a+1]) * pw[-(len-1-a)+off] + (a-b+1);
}
return res;
}
};
template<class T>
void manacher(int n, T arr[], int res[]) {
int i, j, k;
for(i=0,j=0; i<2*n; i+=k, j=max(j-k,0)) {
while(i-j >= 0 && i+j+1 < 2*n && arr[(i-j)/2] == arr[(i+j+1)/2]) ++j;
res[i] = j;
for(k=1; i-k >= 0 && res[i]-k >= 0 && res[i-k] != res[i]-k; ++k)
res[i+k] = min(res[i-k], res[i]-k);
}
}
template<class T>
struct lazySegtreeMinVal{
int N, logN;
T *data;
T *fixval; char *fixed;
T *addval;
void malloc(int maxN){
int i;
for(i=1;i<maxN;i*=2);
data = (T*)std::malloc(sizeof(T)*2*i);
fixval = (T*)std::malloc(sizeof(T)*i);
addval = (T*)std::malloc(sizeof(T)*i);
fixed = (char*)std::malloc(sizeof(char)*i);
}
T& operator[](int i){
return data[N+i];
}
void setN(int n, int zerofill = 1){
int i;
for(i=1,logN=0;i<n;i*=2,logN++);
N = i;
if(zerofill) rep(i,N) data[N+i] = 0;
}
void build(void){
int i;
for(i=N-1;i;i--) data[i] = min(data[2*i],data[2*i+1]);
REP(i,1,N) fixed[i] = 0;
REP(i,1,N) addval[i] = 0;
}
inline void push_one(int a, int sz){
if(fixed[a]){
if(sz > 1){
fixed[a*2] = fixed[a*2+1] = 1;
fixval[a*2] = fixval[a*2+1] = fixval[a];
data[a*2] = data[a*2+1] = fixval[a];
} else {
data[a*2] = data[a*2+1] = fixval[a];
}
fixed[a] = 0;
addval[a] = 0;
return;
}
if(addval[a] != 0){
if(sz > 1){
if(fixed[a*2]) fixval[a*2] += addval[a];
else addval[a*2] += addval[a];
if(fixed[a*2+1]) fixval[a*2+1] += addval[a];
else addval[a*2+1] += addval[a];
data[a*2] += addval[a];
data[a*2+1] += addval[a];
} else {
data[a*2] += addval[a];
data[a*2+1] += addval[a];
}
addval[a] = 0;
return;
}
}
inline void push(int a){
int i, aa;
for(i=logN;i;i--){
aa = a>>i;
push_one(aa, 1<<(i-1));
}
}
inline void build(int a){
while(a > 1){
a /= 2;
if(fixed[a]){
data[a] = fixval[a];
} else {
data[a] = min(data[a*2], data[a*2+1]);
if(addval[a] != 0) data[a] += addval[a];
}
}
}
inline void change(int a, int b, T val){
int aa, bb;
if(a >= b) return;
aa = (a += N);
bb = (b += N);
push(a); push(b-1);
if(a%2) data[a++] = val;
if(b%2) data[--b] = val;
a /= 2;
b /= 2;
while(a < b){
if(a%2) fixed[a]=1, fixval[a]=val, data[a++] = val;
if(b%2) fixed[--b]=1, fixval[b]=val, data[b] = val;
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline void add(int a, int b, T val){
int sz = 1, aa, bb;
if(a >= b) return;
aa = (a += N);
bb = (b += N);
push(a); push(b-1);
if(a%2) data[a++] += val;
if(b%2) data[--b] += val;
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
if(fixed[a]) fixval[a] += val; else addval[a] += val;
data[a++] += val;
}
if(b%2){
b--;
if(fixed[b]) fixval[b] += val; else addval[b] += val;
data[b] += val;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline T getMinVal(int a, int b){
T res;
int sz = 1;
a += N;
b += N;
push(a); push(b-1);
res = std::numeric_limits<T>::max();
while(a < b){
if(a%2) res = min(res, data[a++]);
if(b%2) res = min(res, data[--b]);
a /= 2;
b /= 2;
}
return res;
}
};
int N;
char S[2000000];
int rad[3000000];
int res[1000000];
int ss[3000000], ee[3000000], vv[3000000], nx[1000000];
int get_nx(int i){
if(nx[i]==-1) return i;
if(i==N-1) return nx[i] = N;
return nx[i] = get_nx(nx[i]);
}
int main(){
int i, j, k, st, ed, m, d;
// rollingHash64<char> h;
// lazySegtreeMinVal<int> t;
reader(&N,S);
// h.init(N,S);
// t.malloc(N);
// t.setN(N);
// t.build();
rep(i,N) S[N+i] = S[i];
manacher(2*N, S, rad);
rep(i,4*N){
k = min(N,rad[i]);
if(i%2==0 && k%2==0) k--;
if(i%2==1 && k%2==1) k--;
if(rad[i]==0) continue;
st = i/2 - (k-1)/2;
ed = i/2 + k/2;
m = ed-st+1;
ss[i] = (st-(N-m)+N+N)%N;
ee[i] = (st+N+N)%N;
vv[i] = m;
// rep(j,N-m+1) res[(st+N-j)%N] = max(res[(st+N-j)%N], m);
}
sort(4*N, vv, ss, ee, mem);
rep(i,N+1) nx[i] = -1;
for(i=4*N-1;i>=0;i--){
if(ss[i] <= ee[i]){
k = ss[i];
while(k <= ee[i]){
// writerLn(ss[i],k,ee[i]);
res[k] = max(res[k], vv[i]);
if(nx[k]==-1) nx[k] = k+1;
k = get_nx(k);
}
} else {
k = ss[i];
while(k < N){
// writerLn(ss[i],k,N);
res[k] = max(res[k], vv[i]);
if(nx[k]==-1) nx[k] = k+1;
k = get_nx(k);
}
k = 0;
while(k <= ee[i]){
// writerLn(0,k,ee[i]);
res[k] = max(res[k], vv[i]);
if(nx[k]==-1) nx[k] = k+1;
k = get_nx(k);
}
}
}
REP(i,1,2*N) res[i%N] = max(res[i%N], res[(i-1)%N]-2);
for(i=2*N-2;i>=0;i--) res[i%N] = max(res[i%N], res[(i+1)%N]-2);
rep(i,N) writerLn(res[i]);
return 0;
}
Java Circular Palindromes HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E2 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
char[] s = ns(n);
char[] s2 = new char[2*n];
for(int i = 0;i < n;i++){
s2[i] = s2[i+n] = s[i];
}
int[] pal = palindrome(s2);
// tr(pal, pal.length, n);
long[] es = new long[16*n];
int p = 0;
for(int i = 0;i < 4*n;i+=2){
pal[i] = Math.min(pal[i], n-((n&1)^1));
es[p++] = (long)(i/2)<<32|i;
es[p++] = (long)(i/2+pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n-pal[i]/2-1)<<32|i;
es[p++] = (long)(i/2+n)<<32|i;
}
for(int i = 1;i < 4*n;i+=2){
pal[i] = Math.min(pal[i], n-((n&1)));
es[p++] = (long)(i/2)<<32|i;
es[p++] = (long)(i/2+pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n-pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n)<<32|i;
}
Arrays.sort(es, 0, p);
MaxHeap inc = new MaxHeap(4*n+1);
MaxHeap dec = new MaxHeap(4*n+1);
MaxHeap flat = new MaxHeap(4*n+1);
int[] st = new int[4*n];
int q = 0;
for(int i = 0;i < 2*n-1;i++){
while(q < p && es[q]>>>32 <= i){
int ind = (int)es[q];
if(st[ind] == 0){
inc.add(ind, (pal[ind]&1)-2*i);
}else if(st[ind] == 1){
inc.remove(ind);
flat.add(ind, pal[ind]);
}else if(st[ind] == 2){
flat.remove(ind);
dec.add(ind, pal[ind]+2*i);
}else if(st[ind] == 3){
dec.remove(ind);
}
st[ind]++;
q++;
}
if(i >= n-1){
// tr("i", i);
int max = 0;
if(inc.size() > 0)max = Math.max(inc.max()+2*i, max);
// tr(max);
if(dec.size() > 0)max = Math.max(dec.max()-2*i, max);
// tr(max);
max = Math.max(flat.max(), max);
// tr(max);
out.println(max);
}
}
}
public static class MaxHeap {
public int[] a;
public int[] map;
public int[] imap;
public int n;
public int pos;
public static int INF = Integer.MIN_VALUE;
public MaxHeap(int m)
{
n = m+2;
a = new int[n];
map = new int[n];
imap = new int[n];
Arrays.fill(a, INF);
Arrays.fill(map, -1);
Arrays.fill(imap, -1);
pos = 1;
}
public int add(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}
return ret != -1 ? a[ret] : x;
}
public int update(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}else{
int o = a[ret];
a[ret] = x;
up(ret);
down(ret);
// if(a[ret] < o){
// up(ret);
// }else{
// down(ret);
// }
}
return x;
}
public int remove(int ind)
{
if(pos == 1)return INF;
if(imap[ind] == -1)return INF;
pos--;
int rem = imap[ind];
int ret = a[rem];
map[rem] = map[pos];
imap[map[pos]] = rem;
imap[ind] = -1;
a[rem] = a[pos];
a[pos] = INF;
map[pos] = -1;
up(rem);
down(rem);
return ret;
}
public int max() { return a[1]; }
public int argmax() { return map[1]; }
public int size() { return pos-1; }
private void up(int cur)
{
for(int c = cur, p = c>>>1;p >= 1 && a[p] < a[c];c>>>=1, p>>>=1){
int d = a[p]; a[p] = a[c]; a[c] = d;
int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
e = map[p]; map[p] = map[c]; map[c] = e;
}
}
private void down(int cur)
{
for(int c = cur;2*c < pos;){
int b = a[2*c] > a[2*c+1] ? 2*c : 2*c+1;
if(a[b] > a[c]){
int d = a[c]; a[c] = a[b]; a[b] = d;
int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
e = map[c]; map[c] = map[b]; map[b] = e;
c = b;
}else{
break;
}
}
}
}
public static int[] palindrome(char[] str)
{
int n = str.length;
int[] r = new int[2*n];
int k = 0;
for(int i = 0, j = 0;i < 2*n;i += k, j = Math.max(j-k, 0)){
// normally
while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/2])j++;
r[i] = j;
// skip based on the theorem
for(k = 1;i-k >= 0 && r[i]-k >= 0 && r[i-k] != r[i]-k;k++){
r[i+k] = Math.min(r[i-k], r[i]-k);
}
}
return r;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new E2().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Circular Palindromes HackerRank Solution
#!/bin/python3
import os
import sys
import time
import random
#
# Complete the circularPalindromes function below.
#
def circularPalindromes(s):
#
# Write your code here.
#
t1 = time.monotonic_ns()
os = []
ocs = []
es = []
ecs = []
l = len(s)
b = 3 * s
curchar = '\0'
curstart = 0
curcount = 0
triplets = []
tripstart = 0
for i, c in enumerate(b):
if not i:
curstart = 0
curcount = 1
curchar = c
else:
if c == curchar:
curcount += 1
else:
for j in range(curcount):
triplets.append((curchar, curcount, curstart))
curstart = i
curcount = 1
curchar = c
for i in range(curcount):
triplets.append((curchar, curcount, curstart))
print(time.monotonic_ns() - t1)
# print(triplets)
t2 = time.monotonic_ns()
for i in range(l):
center = l + i
o = -1
if triplets[center][1] % 2 and center == triplets[center][2] + triplets[center][1]//2:
ociinner = triplets[center][1]
ocicenter = i
o = triplets[center][1]
p1 = triplets[center][2] - 1
p2 = triplets[center][2] + triplets[center][1]
while p1 >= 0 and p2 < 3*l and triplets[p1][0] == triplets[p2][0]:
if triplets[p1][1] != triplets[p2][1]:
o += 2*min(triplets[p1][1], triplets[p2][1])
break
o += 2*triplets[p1][1]
p1 -= triplets[p1][1]
p2 += triplets[p2][1]
ocitotal = o
ocs.append((ocitotal,ocicenter,ociinner))
else:
o = 1 + 2*min(center-triplets[center][2], triplets[center][2] + triplets[center][1] - 1 - center)
os.append(min(l,o))
e = 0
if triplets[center][1] % 2 == 0 and center == triplets[center][2] + triplets[center][1]//2:
eciinner = triplets[center][1]
ecicenter = i
# print("Good segment, center={}".format(center))
e = triplets[center][1]
# print("Adding {}".format(triplets[center][1]))
p1 = triplets[center][2] - 1
p2 = triplets[center][2] + triplets[center][1]
while p1 >= 0 and p2 < 3*l and triplets[p1][0] == triplets[p2][0]:
# print("Matching outers: {} {}".format(triplets[p1][0], triplets[p2][0]))
if triplets[p1][1] != triplets[p2][1]:
e += 2*min(triplets[p1][1], triplets[p2][1])
# print("Adding {}".format(2*triplets[p1][1]))
break
e += 2*triplets[p1][1]
# print("Adding {}".format(2*triplets[p1][1]))
p1 -= triplets[p1][1]
p2 += triplets[p2][1]
ecitotal = e
ecs.append((ecitotal,ecicenter,eciinner))
else:
e = 2 + 2*min(center - 1 - triplets[center][2], triplets[center][2] + triplets[center][1] - 1 - center)
es.append(min(l,e))
print(time.monotonic_ns() - t2)
t3 = time.monotonic_ns()
# print(os)
# print(es)
# os1 = []
# es1 = []
# for i in range(l):
# o = -1
# p1 = l + i
# p2 = l + i
# while o <= l - 2 and b[p1] == b[p2]:
# p1 -= 1
# p2 += 1
# o += 2
# os1.append(o)
# e = 0
# p1 = l + i - 1
# p2 = l + i
# while e <= l - 2 and b[p1] == b[p2]:
# p1 -= 1
# p2 += 1
# e += 2
# es1.append(e)
# print(os1)
# print(es1)
# ros = [(o, i) for i, o in enumerate(os)]
# #import operator
# ros = sorted(ros, key=lambda x: x[0], reverse=True)
# res = [(e, i) for i, e in enumerate(es) if e > 0]
# res = sorted(res, key=lambda x: x[0], reverse=True)
rocs = sorted(ocs, key=lambda x: x[0], reverse=True)
print(rocs)
recs = sorted(ecs, key=lambda x: x[0], reverse=True)
print(recs)
# print(res)
print(time.monotonic_ns() - t3)
t4 = time.monotonic_ns()
bests = []
if l % 2:
bests = [max(os[(i+l//2)%l], min(l-1,max(es[(i+l//2)%l],es[(i+l//2+1)%l]))) for i in range(l)]
else:
bests = [max(es[(i+l//2)%l], min(l-1,max(os[(i+l//2)%l],os[(i+l//2-1)%l]))) for i in range(l)]
# print("Length: {}".format(len(bests)))
# print(bests)
# topres = res[:10]
# topros = ros[:10]
# for i in range(l):
# top = bests[i]
# rosi = 0
# while(rosi < len(ros) and ros[rosi][0] > top):
# top = max(top,min(ros[rosi][0],1+ 2*min((ros[rosi][1]-i)%l, (i - 1 - ros[rosi][1])%l)))
# rosi += 1
# resi = 0
# while(resi < len(res) and res[resi][0] > top):
# top = max(top,min(res[resi][0],2*min((res[resi][1]-i)%l, (i - res[resi][1])%l)))
# resi += 1
# bests[i] = top
for i in range(l):
print("Index: {}".format(i))
top = bests[i]
rosi = 0
while(rosi < len(rocs) and rocs[rosi][0] > top):
centerresult = min(rocs[rosi][0],1+2*min((rocs[rosi][1]-i)%l, (i - 1 - rocs[rosi][1])%l))
print("CR1: {}".format(centerresult))
#centerresult = 1 + 2*min(((rocs[rosi][1] + rocs[rosi][0]//2)-(i+l//2))%l, (i+l//2 - (rocs[rosi][1] - rocs[rosi][0]//2)))
# max(i-center-inner//2, center + inner//2 + 1 - i
if centerresult < rocs[rosi][2]:
centerresult = min(rocs[rosi][2],max((i - (rocs[rosi][1] - rocs[rosi][2]//2))%l, (rocs[rosi][1] + rocs[rosi][2]//2 + 1 - i)%l))
top = max(top,min(centerresult,l))
rosi += 1
print("Odd {}".format(top))
resi = 0
while(resi < len(recs) and recs[resi][0] > top):
centerresult = min(recs[resi][0],2*min((recs[resi][1]-i)%l, (i - recs[resi][1])%l))
print("CR2: {}".format(centerresult))
#centerresult = 2*min(((recs[resi][1] + recs[resi][0]//2)-(i+l//2-1))%l, (i+l//2 - (recs[resi][1] - recs[resi][0]//2)))
if centerresult < recs[resi][2]:
centerresult = min(recs[resi][2],max((i - (recs[resi][1] - recs[resi][2]//2))%l, (recs[resi][1] + recs[resi][2]//2 - i)%l))
top = max(top,min(centerresult,l))
resi += 1
bests[i] = top
print("Even {}".format(top))
print(time.monotonic_ns() - t4)
# if not l % 2:
# for i in range(l):
# print(s[i:] + s[:i])
# ep1 = int((i + l/2)) % l
# ep2 = ep1
# top = es[ep1]
# bound = l - 2
# while(bound > top):
# ep1 = (ep1-1)%l
# ep2 = (ep2+1)%l
# top = max(top,min(bound,max(es[ep1],es[ep2])))
# bound -= 2
# op2 = int((i + l/2)) % l
# op1 = int((op2 - 1)) % l
# bound = l - 1
# while(bound > top):
# top = max(top, min(bound, max(os[op1],os[op2])))
# op1 = (op1-1)%l
# op2 = (op2+1)%l
# bound -= 2
# bests.append(top)
# else:
# for i in range(l):
# print(s[i:] + s[:i])
# op1 = int((i + l/2)) % l
# op2 = op1
# top = os[op1]
# bound = l - 2
# while(bound > top):
# op1 = (op1-1)%l
# op2 = (op2+1)%l
# top = max(top,min(bound,max(os[op1],os[op2])))
# bound -= 2
# ep2 = int((i + l/2) + 1) % l
# ep1 = int((ep2-1)) % l
# bound = l - 1
# while(bound > top):
# top = max(top, min(bound, max(es[ep1],es[ep2])))
# ep1 = (ep1-1)%l
# ep2 = (ep2+1)%l
# bound -= 2
# bests.append(top)
# print(bests)
return bests
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
s = input()
# letters = ('a','b','c')
# tester = ""
# for i in range(500000):
# tester += letters[random.randint(0,2)]
# #tester = "a" * 500000
# print(circularPalindromes(tester))
result = circularPalindromes(s)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()
Python 2 Circular Palindromes HackerRank Solution
#!/bin/python3
import os
import sys
import time
import random
#
# Complete the circularPalindromes function below.
#
def circularPalindromes(s):
#
# Write your code here.
#
t1 = time.monotonic_ns()
os = []
ocs = []
es = []
ecs = []
l = len(s)
b = 3 * s
curchar = '\0'
curstart = 0
curcount = 0
triplets = []
tripstart = 0
for i, c in enumerate(b):
if not i:
curstart = 0
curcount = 1
curchar = c
else:
if c == curchar:
curcount += 1
else:
for j in range(curcount):
triplets.append((curchar, curcount, curstart))
curstart = i
curcount = 1
curchar = c
for i in range(curcount):
triplets.append((curchar, curcount, curstart))
print(time.monotonic_ns() - t1)
# print(triplets)
t2 = time.monotonic_ns()
for i in range(l):
center = l + i
o = -1
if triplets[center][1] % 2 and center == triplets[center][2] + triplets[center][1]//2:
ociinner = triplets[center][1]
ocicenter = i
o = triplets[center][1]
p1 = triplets[center][2] - 1
p2 = triplets[center][2] + triplets[center][1]
while p1 >= 0 and p2 < 3*l and triplets[p1][0] == triplets[p2][0]:
if triplets[p1][1] != triplets[p2][1]:
o += 2*min(triplets[p1][1], triplets[p2][1])
break
o += 2*triplets[p1][1]
p1 -= triplets[p1][1]
p2 += triplets[p2][1]
ocitotal = o
ocs.append((ocitotal,ocicenter,ociinner))
else:
o = 1 + 2*min(center-triplets[center][2], triplets[center][2] + triplets[center][1] - 1 - center)
os.append(min(l,o))
e = 0
if triplets[center][1] % 2 == 0 and center == triplets[center][2] + triplets[center][1]//2:
eciinner = triplets[center][1]
ecicenter = i
# print("Good segment, center={}".format(center))
e = triplets[center][1]
# print("Adding {}".format(triplets[center][1]))
p1 = triplets[center][2] - 1
p2 = triplets[center][2] + triplets[center][1]
while p1 >= 0 and p2 < 3*l and triplets[p1][0] == triplets[p2][0]:
# print("Matching outers: {} {}".format(triplets[p1][0], triplets[p2][0]))
if triplets[p1][1] != triplets[p2][1]:
e += 2*min(triplets[p1][1], triplets[p2][1])
# print("Adding {}".format(2*triplets[p1][1]))
break
e += 2*triplets[p1][1]
# print("Adding {}".format(2*triplets[p1][1]))
p1 -= triplets[p1][1]
p2 += triplets[p2][1]
ecitotal = e
ecs.append((ecitotal,ecicenter,eciinner))
else:
e = 2 + 2*min(center - 1 - triplets[center][2], triplets[center][2] + triplets[center][1] - 1 - center)
es.append(min(l,e))
print(time.monotonic_ns() - t2)
t3 = time.monotonic_ns()
# print(os)
# print(es)
# os1 = []
# es1 = []
# for i in range(l):
# o = -1
# p1 = l + i
# p2 = l + i
# while o <= l - 2 and b[p1] == b[p2]:
# p1 -= 1
# p2 += 1
# o += 2
# os1.append(o)
# e = 0
# p1 = l + i - 1
# p2 = l + i
# while e <= l - 2 and b[p1] == b[p2]:
# p1 -= 1
# p2 += 1
# e += 2
# es1.append(e)
# print(os1)
# print(es1)
# ros = [(o, i) for i, o in enumerate(os)]
# #import operator
# ros = sorted(ros, key=lambda x: x[0], reverse=True)
# res = [(e, i) for i, e in enumerate(es) if e > 0]
# res = sorted(res, key=lambda x: x[0], reverse=True)
rocs = sorted(ocs, key=lambda x: x[0], reverse=True)
print(rocs)
recs = sorted(ecs, key=lambda x: x[0], reverse=True)
print(recs)
# print(res)
print(time.monotonic_ns() - t3)
t4 = time.monotonic_ns()
bests = []
if l % 2:
bests = [max(os[(i+l//2)%l], min(l-1,max(es[(i+l//2)%l],es[(i+l//2+1)%l]))) for i in range(l)]
else:
bests = [max(es[(i+l//2)%l], min(l-1,max(os[(i+l//2)%l],os[(i+l//2-1)%l]))) for i in range(l)]
# print("Length: {}".format(len(bests)))
# print(bests)
# topres = res[:10]
# topros = ros[:10]
# for i in range(l):
# top = bests[i]
# rosi = 0
# while(rosi < len(ros) and ros[rosi][0] > top):
# top = max(top,min(ros[rosi][0],1+ 2*min((ros[rosi][1]-i)%l, (i - 1 - ros[rosi][1])%l)))
# rosi += 1
# resi = 0
# while(resi < len(res) and res[resi][0] > top):
# top = max(top,min(res[resi][0],2*min((res[resi][1]-i)%l, (i - res[resi][1])%l)))
# resi += 1
# bests[i] = top
for i in range(l):
print("Index: {}".format(i))
top = bests[i]
rosi = 0
while(rosi < len(rocs) and rocs[rosi][0] > top):
centerresult = min(rocs[rosi][0],1+2*min((rocs[rosi][1]-i)%l, (i - 1 - rocs[rosi][1])%l))
print("CR1: {}".format(centerresult))
#centerresult = 1 + 2*min(((rocs[rosi][1] + rocs[rosi][0]//2)-(i+l//2))%l, (i+l//2 - (rocs[rosi][1] - rocs[rosi][0]//2)))
# max(i-center-inner//2, center + inner//2 + 1 - i
if centerresult < rocs[rosi][2]:
centerresult = min(rocs[rosi][2],max((i - (rocs[rosi][1] - rocs[rosi][2]//2))%l, (rocs[rosi][1] + rocs[rosi][2]//2 + 1 - i)%l))
top = max(top,min(centerresult,l))
rosi += 1
print("Odd {}".format(top))
resi = 0
while(resi < len(recs) and recs[resi][0] > top):
centerresult = min(recs[resi][0],2*min((recs[resi][1]-i)%l, (i - recs[resi][1])%l))
print("CR2: {}".format(centerresult))
#centerresult = 2*min(((recs[resi][1] + recs[resi][0]//2)-(i+l//2-1))%l, (i+l//2 - (recs[resi][1] - recs[resi][0]//2)))
if centerresult < recs[resi][2]:
centerresult = min(recs[resi][2],max((i - (recs[resi][1] - recs[resi][2]//2))%l, (recs[resi][1] + recs[resi][2]//2 - i)%l))
top = max(top,min(centerresult,l))
resi += 1
bests[i] = top
print("Even {}".format(top))
print(time.monotonic_ns() - t4)
# if not l % 2:
# for i in range(l):
# print(s[i:] + s[:i])
# ep1 = int((i + l/2)) % l
# ep2 = ep1
# top = es[ep1]
# bound = l - 2
# while(bound > top):
# ep1 = (ep1-1)%l
# ep2 = (ep2+1)%l
# top = max(top,min(bound,max(es[ep1],es[ep2])))
# bound -= 2
# op2 = int((i + l/2)) % l
# op1 = int((op2 - 1)) % l
# bound = l - 1
# while(bound > top):
# top = max(top, min(bound, max(os[op1],os[op2])))
# op1 = (op1-1)%l
# op2 = (op2+1)%l
# bound -= 2
# bests.append(top)
# else:
# for i in range(l):
# print(s[i:] + s[:i])
# op1 = int((i + l/2)) % l
# op2 = op1
# top = os[op1]
# bound = l - 2
# while(bound > top):
# op1 = (op1-1)%l
# op2 = (op2+1)%l
# top = max(top,min(bound,max(os[op1],os[op2])))
# bound -= 2
# ep2 = int((i + l/2) + 1) % l
# ep1 = int((ep2-1)) % l
# bound = l - 1
# while(bound > top):
# top = max(top, min(bound, max(es[ep1],es[ep2])))
# ep1 = (ep1-1)%l
# ep2 = (ep2+1)%l
# bound -= 2
# bests.append(top)
# print(bests)
return bests
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
s = input()
# letters = ('a','b','c')
# tester = ""
# for i in range(500000):
# tester += letters[random.randint(0,2)]
# #tester = "a" * 500000
# print(circularPalindromes(tester))
result = circularPalindromes(s)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()
C Circular Palindromes HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(char *str,int *a);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
int max(int x,int y);
void update(int x,int y,int z);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
char str[1000001]={0};
int N,NN,a[2000004],tree[2000000],ans[500000],b[500000],c[500000];
int main(){
int i,j;
scanf("%d%s",&NN,str);
strncpy(str+NN,str,NN);
solve(str,a);
init(NN);
for(i=0;i<4*NN;i++)
if(a[i])
if(i%2)
update(i/2-a[i]/2,i/2+a[i]/2,a[i]);
else
update(i/2-a[i]/2,i/2+a[i]/2-1,a[i]);
for(i=0;i<NN;i++){
ans[i]=query(i);
b[i]=ans[i];
c[i]=i;
}
sort_a2(b,c,NN);
for(i=NN;i>=0;i--){
for(j=c[i];1;j=(j-1+NN)%NN)
if(ans[j]-ans[(j-1+NN)%NN]>2)
ans[(j-1+NN)%NN]=ans[j]-2;
else
break;
for(j=c[i];1;j=(j+1)%NN)
if(ans[j]-ans[(j+1)%NN]>2)
ans[(j+1)%NN]=ans[j]-2;
else
break;
}
for(i=0;i<NN;i++)
printf("%d\n",ans[i]);
return 0;
}
void solve(char *str,int *a){
char *p;
int len,R,Ri,i,j,mi;
len=strlen(str);
p=(char*)malloc(2*(len+1)*sizeof(char));
for(i=0;i<len;i++){
p[2*i]='#';
p[2*i+1]=str[i];
}
p[2*i]='#';
p[2*i+1]=0;
a[0]=R=Ri=0;
for(i=1;i<=len*2;i++)
if(i>=R){
if(p[i]!='#')
a[i]=1;
else
a[i]=0;
for(j=i+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else{
mi=2*Ri-i;
if(i+a[mi]>=R || mi==a[mi]){
a[i]=R-i;
for(j=R+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else
a[i]=a[mi];
}
free(p);
return;
}
void init( int n ){
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
void range_increment( int i, int j, int val ){
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] = max(tree[i],val);
if( j % 2 == 0 ) tree[j] = max(tree[j],val);
}
}
int query( int i ){
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans = max(ans,tree[j]);
return ans;
}
int max(int x,int y){
return (x>y)?x:y;
}
void update(int x,int y,int z){
if(z>NN){
int m=x+z/2;
if(z%2)
if(NN%2)
update(m-NN/2,m+NN/2,NN);
else
update(m-NN/2+1,m+NN/2-1,NN-1);
else
if(NN%2)
update(m-NN/2,m+NN/2-1,NN-1);
else
update(m-NN/2,m+NN/2-1,NN);
}
if(y<NN){
range_increment(0,x,z);
range_increment(y+1,NN-1,z);
}
else
range_increment(y-NN+1,x,z);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
Comments 1