HackerRank Circular Palindromes Problem Solution

HackerRank Circular Palindromes Problem Solution

Yashwant Parihar,

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

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

Leave a Reply