We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Circular Palindromes
  5. Discussions

Circular Palindromes

Problem
Submissions
Leaderboard
Discussions

Sort 39 Discussions, By:

recency

Please Login in order to post a comment

  • yashdeora98294
    4 months ago+ 0 comments

    Here is Circular palindromes problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-circular-palindromes-problem-solution.html

    0|
    Permalink
  • SaiDheerajECE
    4 months ago+ 0 comments
    #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;
    }
    
    0|
    Permalink
  • bhautik4avenger4
    8 months ago+ 0 comments

    https://zeroplusfour.com/circular-palindromes/

    Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

    0|
    Permalink
  • madalasa
    9 months ago+ 1 comment

    In this explaination, explained the string "cacbbba" with max substring as '3' only. But there is a combination "acbbbca" which is with max 7. It is not covered

    0|
    Permalink
  • Shaileshshekhar5
    1 year ago+ 0 comments

    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)); }
    

    }

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy