In this HackerRank Circular Palindromes problem solution we have given Northward and Due south, detect all N thou-length rotations of s; for each rotated string, Sk, print the maximum possible length of any palindromic substring of Sk on a new line.

HackerRank Circular Palindromes problem solution

Trouble solution in Python.

#!/bin/python3  import bone import sys import random import bifurcate  # # Complete the circularPalindromes function below. # def get_len(due south, ll, flag):     # use flag = 0 for odd number of messages in palindrome, 1 for even     maxlen = i     l1 = ll - ii     l2 = ll + ane + flag     while l1>=0 and l2 < len(s) and s[l1] == s[l2]:         maxlen += 1         l1 -= 1         l2 += ane     return two*maxlen + flag  def max_pal(s):     # detect the length of the longest palindrome in s     ls = len(south)     maxlen = 1      for ll in range(1, ls):         if s[ll-1] == s[ll]:             newlen = get_len(southward, ll, 0)             if newlen > maxlen:                 maxlen = newlen     for ll in range(ane, ls-i):         if s[ll-1] == s[ll+ane]:             newlen = get_len(south, ll, 1)             if newlen > maxlen:                 maxlen = newlen     render maxlen  def get_len_round_fast(slist, ll, lens):     ls = len(slist)     if ls == 1:         return (slist[0][1], slist[0][2])     commencement = slist[ll][one]     end = slist[ll][2]     l1 = ll - ane     l2 = ll + 1     notdone = True     while notdone and (stop - starting time)<lens and slist[l1 % ls][0] == slist[l2 % ls][0]:         lgth1 = slist[l1][ii]-slist[l1][1]         if lgth1 < 0:             lgth1 += lens         ls2 = l2 % ls         lgth2 = slist[ls2][ii]-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//ii             notdone = False         cease+= lgth2         offset -= lgth2         l1 -= one         l2 += 1 #        impress(l1, l2)     render (start, end)      def compress_string(s):     # replaces strings of contiguous identical characters with (char, #) pairs     #   where # is the terminate of the string sequence     ls = []     cc = '.'     showtime = 0     for ss in range(len(southward)):             if s[ss] != cc: # new char             ls.append((cc, start, ss))             start = ss             cc = south[ss]     ls.append((cc, start, len(due south))) # suspend the terminal characters encountered     ls.popular(0) # start value is a throwaway one     if ls[0][0] == ls[-ane][0]: # stitch the ends, move the start of sequence earlier 0         ls[0] = (ls[0][0], ls[-1][1]-len(southward), ls[0][2])         ls.pop() # remove last element, now that it is combined with the offset     render 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 > i:             if showtime < 0:                 commencement, cease = get-go+lens, stop+lens             if lgth in dict1:                 dict1[lgth].append((beginning, end))             else:                 dict1[lgth]= [(start, stop)]                 bisect.insort(list1, lgth)     for (_, starting time, stop) in slist:         lgth = cease - start         if lgth > 1:             if offset < 0:                 beginning, cease = start+lens, finish+lens             if lgth in dict1:                 if (start, finish) in dict1[lgth]:                     dict1[lgth].remove((start, stop))                 dict1[lgth].suspend((-start, -stop))             else:                 dict1[lgth]= [(-start, -cease)]                 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 # beginning here to await for longest palindrome      for m in range(ls):         maxlgth = i          done = Fake         ks = k + ls         for ind in range(ll, -1, -1): # go backwards through listing of lengths             if washed: # max value already reached for a longer word                 break             lgth = list1[ind]             if lgth < maxlgth: # just shorter words available past here                 intermission             for (beginning, stop) in dict1[lgth]:                 if start<=0 and stop <= 0: # same chars, no need to cut palindrome at both ends #                    print(beginning, stop, k)                     if -start <= one thousand < -stop:                         lgth1 = max(-stop - k, k+start)                      else:                         lgth1 = lgth                     if -starting time < ks <= -stop:                         lgth2 = max(ks + start, -stop - ks)                     else:                         lgth2 = lgth                     #print(lgth1, lgth2)                 else: #                print(lgth, maxlgth, k, start, end)                     if start <= k <= end:                         lgth1 = abs(start+stop-yard-k)                     else:                         lgth1 = lgth                     if start <= ks <= stop:                         lgth2 = abs(start+cease-ks-ks)                     else:                         lgth2 = lgth                 if lgth1 > lgth2:                     lgth1 = lgth2                 if maxlgth < lgth1:                     maxlgth = lgth1 #                    print(maxlgth)                 if lgth1 == lgth:                     washed = True                     break #        print("k=", m, "ml=", maxlgth)         maxes.suspend(maxlgth)     return maxes  def circularPalindromes(s):     #     # Write your lawmaking here.     #     debug = 0     if debug == 0:         return cp(southward)     elif debug == 1:         for two in range(1000):             southward = ""             for jj in range(x):                 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, one]     elif debug == ii:         return cp_gold(s)     else:         (dict1, list1) = make_pal_list(southward)         print(dict1, list1)         return cp_gold(south)                       def rotate_s(s, val):     val = val % len(south)     render s[val:]+s[:val]      def cp_gold(s):     #     # Write your code here.     #     ls = len(s)     maxes = [max_pal(due south)]     for ll in range(one, ls):         due south = rotate_s(s, 1)         maxes.append(max_pal(s))     return maxes       if __name__ == '__main__':     fptr = open(os.environ['OUTPUT_PATH'], 'due west')      n = int(input())      due south = input()      issue = circularPalindromes(due south)      fptr.write('\n'.join(map(str, outcome)))     fptr.write('\due north')      fptr.shut()

{"way":"total","isActive":fake}

Problem solution in Coffee.

import java.io.ByteArrayInputStream; import coffee.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import coffee.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[two*n];         for(int i = 0;i < northward;i++){             s2[i] = s2[i+n] = s[i];         }         int[] pal = palindrome(s2); //        tr(pal, pal.length, n);         long[] es = new long[xvi*n];         int p = 0;         for(int i = 0;i < 4*due north;i+=2){             pal[i] = Math.min(pal[i], northward-((n&1)^i));             es[p++] = (long)(i/2)<<32|i;             es[p++] = (long)(i/2+pal[i]/2)<<32|i;             es[p++] = (long)(i/ii+n-pal[i]/two-i)<<32|i;             es[p++] = (long)(i/2+due north)<<32|i;         }         for(int i = i;i < iv*n;i+=2){             pal[i] = Math.min(pal[i], northward-((n&ane)));             es[p++] = (long)(i/2)<<32|i;             es[p++] = (long)(i/two+pal[i]/2)<<32|i;             es[p++] = (long)(i/2+n-pal[i]/ii)<<32|i;             es[p++] = (long)(i/2+n)<<32|i;         }                  Arrays.sort(es, 0, p);         MaxHeap inc = new MaxHeap(4*north+i);         MaxHeap december = new MaxHeap(4*northward+1);         MaxHeap flat = new MaxHeap(4*n+i);                  int[] st = new int[four*due north];         int q = 0;         for(int i = 0;i < two*due north-one;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] == two){                     flat.remove(ind);                     dec.add(ind, pal[ind]+two*i);                 }else if(st[ind] == 3){                     december.remove(ind);                 }                 st[ind]++;                 q++;             }             if(i >= n-ane){ //                tr("i", i);                 int max = 0;                 if(inc.size() > 0)max = Math.max(inc.max()+2*i, max); //                tr(max);                 if(december.size() > 0)max = Math.max(dec.max()-ii*i, max); //                tr(max);                 max = Math.max(flat.max(), max); //                tr(max);                 out.println(max);             }         }     }     public static form MaxHeap {         public int[] a;         public int[] map;         public int[] imap;         public int due north;         public int pos;         public static int INF = Integer.MIN_VALUE;                  public MaxHeap(int m)         {             northward = m+ii;             a = new int[north];             map = new int[n];             imap = new int[n];             Arrays.fill(a, INF);             Arrays.fill up(map, -1);             Arrays.fill(imap, -one);             pos = 1;         }                  public int add(int ind, int ten)         {             int ret = imap[ind];             if(imap[ind] < 0){                 a[pos] = x; map[pos] = ind; imap[ind] = pos;                 pos++;                 upwards(pos-1);             }             return ret != -i ? a[ret] : ten;         }                  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] = ten;                 upward(ret);                 down(ret); //                if(a[ret] < o){ //                    up(ret); //                }else{ //                    downward(ret); //                }             }             render x;         }                  public int remove(int ind)         {             if(pos == i)render 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] = -i;                          upwards(rem);             downward(rem);             return ret;         }                  public int max() { return a[1]; }         public int argmax() { return map[1]; }         public int size() {    return pos-1; }                  individual void up(int cur)         {             for(int c = cur, p = c>>>1;p >= 1 && a[p] < a[c];c>>>=1, p>>>=ane){                 int d = a[p]; a[p] = a[c]; a[c] = d;                 int due east = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = east;                 eastward = map[p]; map[p] = map[c]; map[c] = east;             }         }                  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+one;                 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] = east;                     c = b;                 }else{                     break;                 }             }         }     }          public static int[] palindrome(char[] str)     {         int north = str.length;         int[] r = new int[2*n];         int thousand = 0;         for(int i = 0, j = 0;i < 2*due north;i += k, j = Math.max(j-chiliad, 0)){             // normally             while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/two])j++;             r[i] = j;                          // skip based on the theorem             for(chiliad = one;i-k >= 0 && r[i]-k >= 0 && r[i-g] != r[i]-one thousand;k++){                 r[i+k] = Math.min(r[i-yard], r[i]-yard);             }         }         return r;     }           void run() throws Exception     {         is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());         out = new PrintWriter(Organisation.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(); }          individual byte[] inbuf = new byte[1024];     individual int lenbuf = 0, ptrbuf = 0;          private int readByte()     {         if(lenbuf == -1)throw new InputMismatchException();         if(ptrbuf >= lenbuf){             ptrbuf = 0;             try { lenbuf = is.read(inbuf); } take hold of (IOException due east) { throw new InputMismatchException(); }             if(lenbuf <= 0)render -1;         }         return inbuf[ptrbuf++];     }          private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }     individual 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 Cord ns()     {         int b = skip();         StringBuilder sb = new StringBuilder();         while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')             sb.appendCodePoint(b);             b = readByte();         }         return sb.toString();     }          individual char[] ns(int n)     {         char[] buf = new char[due north];         int b = skip(), p = 0;         while(p < due north && !(isSpaceChar(b))){             buf[p++] = (char)b;             b = readByte();         }         return north == p ? buf : Arrays.copyOf(buf, p);     }          individual char[][] nm(int n, int m)     {         char[][] map = new char[due north][];         for(int i = 0;i < due north;i++)map[i] = ns(m);         render map;     }          private int[] na(int due north)     {         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()) != -i && !((b >= '0' && b <= '9') || b == '-'));         if(b == '-'){             minus = truthful;             b = readByte();         }                  while(true){             if(b >= '0' && b <= '9'){                 num = num * x + (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)); } }

{"fashion":"full","isActive":fake}

Problem solution in C++.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <stdio.h> #include <string.h>  using namespace std;   const int MAXN = 5e5, MAXX = MAXN << ane, MAXLEAVES = 1 << nineteen;  char Southward[MAXX + 1]; int R[ii][MAXX + 1], fsize, T[2][MAXX + 1];   void manacher(const int length, const int rx) {      register int i, j, 1000; int *table = R[rx];      for (i = j = 0; i < length; i += g, j = max(j - chiliad, 0)) {          while (i - j >= 0 && i + j + rx < length && S[i - j] == Due south[i + j + rx])              ++j;          table[i] = j;          for (k = one; k < j && table[i - thousand] != table[i] - m; ++k) {              table[i + grand] = min(tabular array[i - k], table[i] - chiliad);         }      }  }   int tree[(MAXLEAVES << 1) + 1], rval, ileft, iright, leaves;  void update_tree(const int x, const int left, const int right) {      if (ileft > right || iright < left) { return; } if (ileft <= left && right <= iright) {          //node completely inside the update interval          tree[x] = max(tree[x], rval);      } else {          int mid = (left + right) >> ane;          update_tree(x << 1, left, mid);          update_tree((10 << 1) + ane, mid + 1, right);      }  }   void adjust_and_gather(const int pos, const int parity) {      int &ptr = R[parity][pos];      int diff = (ptr << i) - (!parity) - fsize, lx, rx, flen;      if (diff > 0) {          diff += (diff & ane);         ptr -= unequal >> 1;      }      lx = pos - ptr + one;     rx = pos + ptr - (parity == 0); flen = (ptr << 1) - (!parity);      if ((parity == 0 && ptr > 1) || (parity == one && ptr > 0)) {          T[0][lx] = max(T[0][lx], flen); T[1][rx] = max(T[1][rx], flen);         ileft = max(0, rx - fsize + 1), iright = min(fsize - 1, 60);          rval = flen;          update_tree(i, 0, leaves - 1);      }  }   inline void process_manacher_table(const int length) {      for (register int i = 0; i < length; ++i) {          adjust_and_gather(i, 0); //odd length;          adjust_and_gather(i, 1); //even length;      }  }  inline int read_tree(const int pos) {      annals int x = pos + leaves;      int result = ane;      while (x) {          result = max(effect, tree[ten]);         10 >>= 1;      }      return upshot;  }  inline void init_leaves(const int northward) {      leaves = ane; while (leaves < due north)      {          leaves <<= i;      }  }  int main() {      register int North, i, respond;      scanf("%d%s", &Northward, South);      memcpy(South + North, South, (North - 1) * sizeof(char));      init_leaves(N);      fsize = N, N = (N << 1) - 1;      manacher(N, 0); //odd length;     manacher(Northward, 1); //even length;      process_manacher_table(North);      for (i = 1; i < N; ++i) {         T[0][i] = max(T[0][i], T[0][i - 1] - ii);          T[1][North - i - 1] = max(T[1][N - i - 1], T[i][N - i] - two);      }      for (i = 0; i < fsize; ++i) {          answer = read_tree(i);          answer = max(answer, T[0][i]);         reply = max(reply, T[1][i + fsize - 1]);          printf("%d\n", answer);      }      return 0; }

{"manner":"full","isActive":fake}

Problem solution in C.

#include <stdio.h> #include <stdlib.h> #include <cord.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 ten,int y); void update(int 10,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%southward",&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]/ii,a[i]);       else         update(i/2-a[i]/two,i/2+a[i]/ii-one,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-one+NN)%NN)       if(ans[j]-ans[(j-1+NN)%NN]>ii)         ans[(j-ane+NN)%NN]=ans[j]-2;       else         break;     for(j=c[i];i;j=(j+one)%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\north",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(ii*(len+1)*sizeof(char));   for(i=0;i<len;i++){     p[two*i]='#';     p[2*i+one]=str[i];   }   p[2*i]='#';   p[2*i+1]=0;   a[0]=R=Ri=0;   for(i=one;i<=len*2;i++)     if(i>=R){       if(p[i]!='#')         a[i]=i;       else         a[i]=0;       for(j=i+1;1;j++)         if(j<=two*len && two*i-j>=0 && p[j]==p[two*i-j]){           if(p[j]!='#')             a[i]+=two;         }         else{           Ri=i;           R=j-i;           pause;         }     }     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]+=two;           }           else{             Ri=i;             R=j-1;             intermission;           }       }       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 < Due north + n; i++ ) tree[i] = 0; } void range_increment( int i, int j, int val ){   for( i += N, j += Northward; i <= j; i = ( i + 1 ) / 2, j = ( j - ane ) / 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 + Northward; j; j /= 2 ) ans = max(ans,tree[j]);   return ans; } int max(int x,int y){   return (10>y)?x:y; } void update(int x,int y,int z){   if(z>NN){     int m=x+z/two;     if(z%2)       if(NN%2)         update(m-NN/2,m+NN/ii,NN);       else         update(m-NN/two+one,grand+NN/2-ane,NN-1);     else       if(NN%2)         update(m-NN/2,one thousand+NN/2-1,NN-1);       else         update(m-NN/2,thousand+NN/two-one,NN);   }   if(y<NN){     range_increment(0,10,z);     range_increment(y+1,NN-one,z);   }   else     range_increment(y-NN+one,10,z);   render; } 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(grand*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<yard;i++){     left_a[i]=a[i];     left_b[i]=b[i];   }   for(i=0;i<size-thou;i++){     right_a[i]=a[i+g];     right_b[i]=b[i+one thousand];   }   sort_a2(left_a,left_b,yard);   sort_a2(right_a,right_b,size-m);   merge2(a,left_a,right_a,b,left_b,right_b,k,size-chiliad);   gratuitous(left_a);   gratis(right_a);   costless(left_b);   free(right_b);   render; } 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; }

{"mode":"full","isActive":imitation}