Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Circular Palindromes Problem Solution

HackerRank Circular Palindromes Problem Solution

Posted on May 1, 2023May 1, 2023 By Yashwant Parihar No Comments on HackerRank Circular Palindromes Problem Solution

In this post, we will solve HackerRank Circular Palindromes Problem Solution.

A palindrome is a string that reads the same from left to right as it does from right to left.
Given a string, S, of N lowercase English letters, we define a k-length rotation as cutting the first k characters from the beginning of S and appending them to the end of S. For each S. there are N possible k-length rotations (where 0 < k < N). See the Explanation section for examples.
Given N and S, find all N k-length rotations of S; for each rotated string, S. print the maximum possible length of any palindromic substring of S on a new line.
Input Format
The first line contains an integer, N (the length of S). The second line contains a single string, S.

Output Format
There should be N lines of output, where each line k contains an integer denoting the
maximum length of any palindromic substring of rotation S.

Sample Input 0

13
aaaaabbbbaaaa

Sample Output 0

12
12
10
8
8
9
11
13
11
9
8
8
10

Sample Input 1

7
cacbbba

Sample Output 1

3
3
3
3
3
3
3

Sample Input 2

12
eededdeedede

Sample Output 2

5
7
7
7
7
9
9
9
9
7
5
4

Explanation
Consider Sample Case 1, where S = “cacbbba”.
The possible rotations, Sk, for string S are:
So = “cacbbba”.
S₁ = “acbbbac”
S2=”cbbbaca”
S3 = “bbbacac”
S4= “bbacacb”
S5 = “bacacbb”
Se=”acacbbb”
The longest palindromic substrings for each S are:
So: “cac” and “bbb”, so we print their length (3) on a new line.
S₁: “bbb”, so we print its length (3) on a new line.
S2: “bbb” and “aca”, so we print their length (3) on a new line.
S3: “bbb”, “aca”, and “cac”, so we print their length (3) on a new line.
S4: “aca” and “cac”, so we print their length (3) on a new line. S5: “aca” and “cac”, so we print their length (3) on a new line.
S6: “aca”, “cac”, and “bbb”, so we print their length (3) on a new line.

HackerRank Circular Palindromes Problem Solution
HackerRank Circular Palindromes Problem Solution

Table of Contents

  • Circular Palindromes C Solution
  • Circular Palindromes C++ Solution
  • Circular Palindromes C Sharp Solution
  • Circular Palindromes Java Solution
  • Circular Palindromes JavaScript Solution
  • Circular Palindromes Python Solution

Circular Palindromes C 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;
}

Circular Palindromes C++ 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;
}

Circular Palindromes C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'circularPalindromes' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts STRING s as parameter.
     */

     private static char[] S; private static int[][] R;

        private static ValueTuple<int, int>[] tp;
        private static int fsize, ileft;

        public static List<int> circularPalindromes(string s)
        {
            int N = s.Length, m = 2 * N - 1;

            tp = new ValueTuple<int, int>[N];

            S = new char[m]; R = new int[2][];

            for (int i = 0; i < 2; i++)
                R[i] = new int[m];


            s.ToCharArray().CopyTo(S, 0);
            s.Substring(0, N - 1).ToCharArray().CopyTo(S, N);


            fsize = N; N = (N << 1) - 1;
            manacher(N, 0);
            manacher(N, 1);

            process_manacher_table(N);
            List<int> res = new List<int>();
            if (tp[0].Item2 == 0) res.Add(1);
            else res.Add(tp[0].Item2);
            int cur = res[0], cur2 = tp[0].Item1;
            for (int i = 1; i < fsize; i++)
            {
                cur2--;
                cur = cur2 > 0 ? cur : cur - 2 > 0 ? cur - 2 : 1;
                if (cur > tp[i].Item2)
                {
                    res.Add(cur);
                    int a2 = tp[i].Item2;
                    int a1 = tp[i].Item1;
                    if (cur - ((a1 - cur2) * 2) < a2)
                    {
                        int z = (cur - a2) / 2, v1 = z + i + 1;
                        if (v1 < fsize) upDate(a1 - cur2 - z, a2, v1);
                    }
                } 
                else
                {
                    int a2 = tp[i].Item2;
                    int a1 = tp[i].Item1;
                    if (a2 - ((cur2 - a1) * 2) < cur)
                    {
                        int z = (a2 - cur) / 2, v1 = z + i + a1;
                        if (v1 < fsize) upDate(cur2 - a1 - z, cur, v1);
                    }
                    cur = tp[i].Item2;
                    res.Add(cur);
                    cur2 = tp[i].Item1;
                    int ii = 1;
                    while (i - ii >= 0 && cur - 2 * ii > res[i - ii])
                    {
                        res[i - ii] = cur - 2 * ii;
                        ii++;
                    }

                }

            }

           
            return res;
        }



        private static void process_manacher_table(int n)
        {
            for (int i = 0; i < n; ++i)
            {
                adjust_and_gather(i, 0);
                adjust_and_gather(i, 1);
            }
        }

        private static void adjust_and_gather(int pos, int parity)
        {
            int ptr = R[parity][pos];
            if ((parity == 0 && ptr == 1) || (parity == 1 && ptr == 0)) return;

            int flen = (ptr << 1) - (parity ^ 1), lx;
            if (flen > fsize) flen = (fsize - parity) %2== 1 ? fsize : fsize - 1;
            
            ptr = (flen+1) / 2;
            lx = pos - ptr + 1;
            ileft = Math.Max(0, lx - (fsize - flen));
            int same = lx - ileft + 1;

            upDate(same, flen, ileft);


        }

        private static void upDate(int v, int flen, int ileft)
        {
            int a1 = tp[ileft].Item1;
            int a2 = tp[ileft].Item2;
            if (a2 >= flen && a2 - ((v - a1) * 2) > flen)
                return;
            else if (a2 < flen && flen - ((a1 - v) * 2) > a2)
                tp[ileft] = (v, flen);
            else if (a2 < flen && flen - ((a1 - v) * 2) < a2)
            {
                tp[ileft] = (v, flen);
                int z = (flen - a2) / 2, v1 = z + ileft + v;
                if (v1 < fsize)upDate(a1 - v - z, a2, v1);
            }
            else if (a2 > flen && a2 - ((v - a1) * 2) < flen)
            {
                int z = (a2 - flen) / 2, v1 = z + ileft + a1;
                if (v1 < fsize) upDate(v - a1 - z, flen, v1);
            }
            else if (a2 == flen && v > a1) tp[ileft] = (v, flen);

        }

        private static void manacher(int length, int rx)
        {
            int i, j, k; var table = R[rx];
            for (i = j = 0; i < length; i += k, j = Math.Max(j - k, 0))
            {
                while (i - j >= 0 && i + j + rx < length && S[i - j] == S[i + j + rx])
                    ++j;
                table[i] = j;
                for (k = 1; k < j && table[i - k] != table[i] - k; ++k)
                {
                    table[i + k] = Math.Min(table[i - k], table[i] - k);
                }
            }

        }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine().Trim());

        string s = Console.ReadLine();

        List<int> result = Result.circularPalindromes(s);

        textWriter.WriteLine(String.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

Circular Palindromes Java 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)); }
}

Circular Palindromes JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'circularPalindromes' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts STRING s as parameter.
 */

function circularPalindromes(s) {
    s = s.split('');

    let currentLength, equalsLength, j1, j2;
    const length = s.length;
    const length2 = s.length - 1;
    const largest = new Array(s.length).fill(0);

    for (let i = 0; i < s.length; i++) {
        currentLength = 1;
        j1 = (i < 1) ? length2 : i - 1;
        j2 = (i >= length2) ? 0 : i + 1;

        while (s[i] === s[j2] && currentLength < length) {
            currentLength++;
            if (++j2 >= length) j2 = 0;
        }
        equalsLength = currentLength;

        if (currentLength > 1) {
            checkEqual(largest, i, currentLength);
            i += currentLength - 1;
        }

        while (s[j1] === s[j2] && currentLength < length && j1 !== j2) {
            currentLength += 2;
            if (--j1 < 0) j1 = length2;
            if (++j2 >= length) j2 = 0;
        }

        if (currentLength > equalsLength) {
            if(++j1 >= length) j1 = 0;
            checkLargest(largest, j1, currentLength, equalsLength);
        }
    }

    return largest;
}

function checkEqual(largest, position, length) {
    const limit = position + length;
    const middle = position + (length >> 1);
    const even = (length & 1) === 0;

    for (let i = (position - largest.length + length < 0 ? 0 : position - largest.length + length); i < position; i++) {
        if (largest[i] < length)  largest[i] = length;
    }

    for (let i = position + length; i < largest.length; i++) {
        if (largest[i] < length) largest[i] = length;
    }

    for (let i = position, j = position; i < limit; i++, j++) {
        if (j >= largest.length) j = i % largest.length;
        if (largest[j] < length) largest[j] = length;
        if (i < middle){
            length--;
        } else if (i > middle) {
            length++;
        } else if (even) {
            length++;
        }
    }
}

function checkLargest(largest, position, length, equalsLength) {
    const limit1 = position + (length >> 1) - (equalsLength >> 1);
    const limit2 = position + length;

    for (let i = (position - largest.length + length < 0 ? 0 : position - largest.length + length); i < position; i++) {
        if (largest[i] < length) largest[i] = length;
    }

    for (let i = position + length; i < largest.length; i++) {
        if (largest[i] < length)  largest[i] = length;
    }

    for (let i = position, j = position; i < limit1; i++, j++) {
        if (j >= largest.length) j = i % largest.length;
        if (largest[j] < length) largest[j] = length;
        length -= 2;
    }

    for (let i = limit1 + equalsLength, j = limit1 + equalsLength; i < limit2; i++, j++) {
        if (j >= largest.length) j = i % largest.length;
        if (largest[j] < length) largest[j] = length;
        length += 2;
    }
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    const s = readLine();

    const result = circularPalindromes(s);

    ws.write(result.join('\n') + '\n');

    ws.end();
}

Circular Palindromes Python Solution

#!/bin/python3

import os
import sys
import random
import bisect

#
# Complete the circularPalindromes function below.
#
def get_len(s, ll, flag):
    # use flag = 0 for odd number of letters in palindrome, 1 for even
    maxlen = 1
    l1 = ll - 2
    l2 = ll + 1 + flag
    while l1>=0 and l2 < len(s) and s[l1] == s[l2]:
        maxlen += 1
        l1 -= 1
        l2 += 1
    return 2*maxlen + flag

def max_pal(s):
    # find the length of the longest palindrome in s
    ls = len(s)
    maxlen = 1 
    for ll in range(1, ls):
        if s[ll-1] == s[ll]:
            newlen = get_len(s, ll, 0)
            if newlen > maxlen:
                maxlen = newlen
    for ll in range(1, ls-1):
        if s[ll-1] == s[ll+1]:
            newlen = get_len(s, ll, 1)
            if newlen > maxlen:
                maxlen = newlen
    return maxlen

def get_len_round_fast(slist, ll, lens):
    ls = len(slist)
    if ls == 1:
        return (slist[0][1], slist[0][2])
    start = slist[ll][1]
    end = slist[ll][2]
    l1 = ll - 1
    l2 = ll + 1
    notdone = True
    while notdone and (end - start)<lens and slist[l1 % ls][0] == slist[l2 % ls][0]:
        lgth1 = slist[l1][2]-slist[l1][1]
        if lgth1 < 0:
            lgth1 += lens
        ls2 = l2 % ls
        lgth2 = slist[ls2][2]-slist[ls2][1]
        if lgth2 < 0:
            lgth2 += lens
        lmax = lens - (end-start)
        if lgth1 != lgth2:
            notdone = False
        # make lgth2 the smaller for subsequent calculations
        if lgth1 < lgth2:
            lgth2 = lgth1
        if lgth2 + lgth2 > lmax:
            lgth2 = lmax//2
            notdone = False
        end+= lgth2
        start -= lgth2
        l1 -= 1
        l2 += 1
#        print(l1, l2)
    return (start, end)
    
def compress_string(s):
    # replaces strings of contiguous identical characters with (char, #) pairs
    #   where # is the end of the string sequence
    ls = []
    cc = '.'
    start = 0
    for ss in range(len(s)):    
        if s[ss] != cc: # new char
            ls.append((cc, start, ss))
            start = ss
            cc = s[ss]
    ls.append((cc, start, len(s))) # append the last characters encountered
    ls.pop(0) # first value is a throwaway one
    if ls[0][0] == ls[-1][0]: # stitch the ends, move the start of sequence before 0
        ls[0] = (ls[0][0], ls[-1][1]-len(s), ls[0][2])
        ls.pop() # remove last element, now that it is combined with the first
    return ls

        
def make_pal_dict(slist, lens):
    ls = len(slist)
    dict1 = {}
    list1 = []
    for ll in range(ls):
        (start, stop) = get_len_round_fast(slist, ll, lens)
#        print(ll, start, stop)
        lgth = stop - start
        if lgth > 1:
            if start < 0:
                start, stop = start+lens, stop+lens
            if lgth in dict1:
                dict1[lgth].append((start, stop))
            else:
                dict1[lgth]= [(start, stop)]
                bisect.insort(list1, lgth)
    for (_, start, stop) in slist:
        lgth = stop - start
        if lgth > 1:
            if start < 0:
                start, stop = start+lens, stop+lens
            if lgth in dict1:
                if (start, stop) in dict1[lgth]:
                    dict1[lgth].remove((start, stop))
                dict1[lgth].append((-start, -stop))
            else:
                dict1[lgth]= [(-start, -stop)]
                bisect.insort(list1, lgth)        
    return (dict1, list1)

        
def cp(s):
    ls = len(s)
    slist = compress_string(s)
#    print(slist)
    (dict1, list1) = make_pal_dict(slist, ls)
#    print(dict1, list1)
    maxes = [] # value for k = 0
    ll = len(list1)-1 # start here to look for longest palindrome 
    for k in range(ls):
        maxlgth = 1 
        done = False
        ks = k + ls
        for ind in range(ll, -1, -1): # go backwards through list of lengths
            if done: # max value already reached for a longer word
                break
            lgth = list1[ind]
            if lgth < maxlgth: # only shorter words available past here
                break
            for (start, stop) in dict1[lgth]:
                if start<=0 and stop <= 0: # same chars, no need to cut palindrome at both ends
#                    print(start, stop, k)
                    if -start <= k < -stop:
                        lgth1 = max(-stop - k, k+start) 
                    else:
                        lgth1 = lgth
                    if -start < ks <= -stop:
                        lgth2 = max(ks + start, -stop - ks)
                    else:
                        lgth2 = lgth
                    #print(lgth1, lgth2)
                else:
#                print(lgth, maxlgth, k, start, stop)
                    if start <= k <= stop:
                        lgth1 = abs(start+stop-k-k)
                    else:
                        lgth1 = lgth
                    if start <= ks <= stop:
                        lgth2 = abs(start+stop-ks-ks)
                    else:
                        lgth2 = lgth
                if lgth1 > lgth2:
                    lgth1 = lgth2
                if maxlgth < lgth1:
                    maxlgth = lgth1
#                    print(maxlgth)
                if lgth1 == lgth:
                    done = True
                    break
#        print("k=", k, "ml=", maxlgth)
        maxes.append(maxlgth)
    return maxes

def circularPalindromes(s):
    #
    # Write your code here.
    #
    debug = 0
    if debug == 0:
        return cp(s)
    elif debug == 1:
        for ii in range(1000):
            s = ""
            for jj in range(10):
                s += chr(97 + random.randrange(0, 26))
            r1 = cp(s) 
            r = cp_gold(s)
            if r1 != r:
                print(r1, "should be", r, "for", s)
        return [1, 1, 1]
    elif debug == 2:
        return cp_gold(s)
    else:
        (dict1, list1) = make_pal_list(s)
        print(dict1, list1)
        return cp_gold(s)
                
    
def rotate_s(s, val):
    val = val % len(s)
    return s[val:]+s[:val]
    
def cp_gold(s):
    #
    # Write your code here.
    #
    ls = len(s)
    maxes = [max_pal(s)]
    for ll in range(1, ls):
        s = rotate_s(s, 1)
        maxes.append(max_pal(s))
    return maxes

    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    s = input()

    result = circularPalindromes(s)

    fptr.write('\n'.join(map(str, result)))
    fptr.write('\n')

    fptr.close()
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Super Functional Strings Solution
Next Post: HackerRank Similar Strings Problem Solution

Related Posts

HackerRank Chocolate Feast Problem Solution HackerRank Chocolate Feast Problem Solution c
HackerRank Red Knight's Shortest Path Problem Solution HackerRank Red Knight’s Shortest Path Solution c
HackerRank Alex vs Fedor Problem Solution HackerRank Alex vs Fedor Problem Solution c
HackerRank New Year Present Problem Solution HackerRank New Year Present Problem Solution c
HackerRank Longest Mod Path Problem Solution HackerRank Longest Mod Path Problem Solution c
HackerRank Circular Array Rotation Problem Solution HackerRank Circular Array Rotation Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme