- Prepare
- Algorithms
- Strings
- Circular Palindromes
- Discussions
Circular Palindromes
Circular Palindromes
+ 0 comments Here is my soluton in java, javascript, python, C, C++, Csharp HackerRank Circular Palindromes Problem Solution
+ 0 comments !/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) 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 lsdef 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 **python solution ** passes all test cases *
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()
+ 0 comments Here is the soluyion of Circular Palindromes Click Here
+ 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 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; }
Sort 42 Discussions, By:
Please Login in order to post a comment