Table of Contents
String Function Calculation – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ String Function Calculation HackerRank Solution
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 201000;
int wa[N], wb[N], ws[N*2], wv[N];
int Rank[N], sa[N], height[N], r[N];
char s[N];
int cmp( int* r, int a, int b, int L ){
return r[a]== r[b] && r[a+ L]== r[b+ L];
}
long long mul(long long x,long long y) {
return x * y;
}
void da( int* r, int* sa, int n, int m ){
int i, j, p, *x= wa, *y= wb, *t;
for( i= 0; i< m; ++i ) ws[i]= 0;
for( i= 0; i< n; ++i ) ws[ x[i]= r[i] ]++;
for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
for( i= n- 1; i>= 0; i-- ) sa[ --ws[ x[i] ] ]= i;
for( j= 1, p= 1; p< n; j*= 2, m= p ){
for( p= 0, i= n- j; i< n; ++i ) y[p++]= i;
for( i= 0; i< n; ++i )
if( sa[i]>= j ) y[p++]= sa[i]- j;
for( i= 0; i< n; ++i ) wv[i]= x[y[i]];
for( i= 0; i< m; ++i ) ws[i]= 0;
for( i= 0; i< n; ++i ) ws[ wv[i] ]++;
for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
for( i= n- 1; i>= 0; i-- ) sa[ --ws[ wv[i] ] ]= y[i];
t= x, x= y, y= t, p= 1; x[ sa[0] ]= 0;
for( i= 1; i< n; ++i )
x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;
}
}
long long largestRectangleArea(vector<int> &height) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int n = height.size();
long long result = 0;
stack<int> s;
for (int i = 0; i < n; ++i) {
//printf("%d\n",height[i]);
while ((!s.empty()) && (height[s.top()] > height[i])) {
int h = height[s.top()];
s.pop();
result = max(result, mul((i - (s.empty()?(-1):s.top())) , h));
}
s.push(i);
}
while (!s.empty()) {
int h = height[s.top()];
s.pop();
//printf("h = %d\n",h);
result = max(result, mul((n - (s.empty()?(-1):s.top())) , h));
}
return result;
}
void callheight( int* r, int*sa, int n ){
int i, j, k= 0;
for( i= 1; i<= n; ++i ) Rank[ sa[i] ]= i;
for( i= 0; i< n; height[ Rank[i++] ]= k )
for( k?k--:0, j= sa[ Rank[i]- 1]; r[i+k]== r[j+k]; k++ );
}
int main(){
scanf("%s",s );
int n = strlen(s);
for(int i= 0; i < n; ++i ){
r[i] = s[i] - 'a' + 1;
}
r[n]= 0;
da( r, sa, n + 1, 27);
callheight( r, sa, n );
vector<int> a;
for (int i = 0; i <= n; ++i) {
//printf("%d\n",height[i]);
a.push_back(height[i]);
}
printf("%lld\n", max((long long) n, largestRectangleArea(a)));
return 0;
}
Java String Function Calculation HackerRank Solution
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Solution {
static class SuffixAutomata {
static class Vertex {
Vertex suffixLink = null;
Vertex[] edges;
int log = 0;
int terminals;
boolean visited;
public Vertex(Vertex o, int log) {
edges = o.edges.clone();
this.log = log;
}
public Vertex(int log) {
edges = new Vertex[26];
this.log = log;
}
long dp() {
if (visited) {
return 0;
}
visited = true;
long r = 0;
for (Vertex v : edges) {
if (v != null) {
r = Math.max(r, v.dp());
terminals += v.terminals;
}
}
return Math.max(r, 1L * log * terminals);
}
}
Vertex root, last;
public SuffixAutomata(String str) {
last = root = new Vertex(0);
for (int i = 0; i < str.length(); i++) {
addChar(str.charAt(i));
}
addTerm();
}
private void addChar(char c) {
Vertex cur = last;
last = new Vertex(cur.log + 1);
while (cur != null && cur.edges[c - 'a'] == null) {
cur.edges[c - 'a'] = last;
cur = cur.suffixLink;
}
if (cur != null) {
Vertex q = cur.edges[c - 'a'];
if (q.log == cur.log + 1) {
last.suffixLink = q;
} else {
Vertex r = new Vertex(q, cur.log + 1);
r.suffixLink = q.suffixLink;
q.suffixLink = r;
last.suffixLink = r;
while (cur != null) {
if (cur.edges[c - 'a'] == q) {
cur.edges[c - 'a'] = r;
} else {
break;
}
cur = cur.suffixLink;
}
}
} else {
last.suffixLink = root;
}
}
private void addTerm() {
Vertex cur = last;
while (cur != null) {
cur.terminals++;
cur = cur.suffixLink;
}
}
}
public static void solve(Input in, PrintWriter out) throws IOException {
String s = in.next();
SuffixAutomata a = new SuffixAutomata(s);
out.println(a.root.dp());
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
Python 3 String Function Calculation HackerRank Solution
from itertools import groupby
from operator import itemgetter
def SuffixArray(tx, _step=16):
size = len(tx); step = min(max(_step, 1), size)
sa = sorted(range(size), key=lambda i: tx[i:i + step])
grpstart = [False]*size+[True]
rsa = [None]*size
stgrp, igrp = '', 0
for i, pos in enumerate(sa):
st = tx[pos:pos + step]
if st != stgrp:
grpstart[igrp] = (igrp < i - 1); stgrp = st; igrp = i
rsa[pos] = igrp; sa[i] = pos
grpstart[igrp] = (igrp < size - 1 or size == 0)
while grpstart.index(True) < size:
nextgr = grpstart.index(True)
while nextgr < size:
igrp = nextgr; nextgr = grpstart.index(True, igrp + 1); glist = []
for ig in range(igrp, nextgr):
pos = sa[ig]
if rsa[pos] != igrp: break
newgr = rsa[pos + step] if pos + step < size else -1
glist.append((newgr, pos))
glist.sort()
for ig, g in groupby(glist, key=itemgetter(0)):
g = [x[1] for x in g]; sa[igrp:igrp + len(g)] = g
grpstart[igrp] = (len(g) > 1)
for pos in g: rsa[pos] = igrp
igrp += len(g)
step *= 2
return sa, rsa
def LCPArray(tx, sa = None, rsa = None):
if sa == None: sa, rsa = SuffixArray(tx)
size = len(tx)
lcp = [None]*size; h = 0
for i in range(size):
if rsa[i] > 0:
j = sa[rsa[i] - 1]
while i+h<size and j+h<size and tx[i+h] == tx[j+h]: h += 1
lcp[rsa[i]] = h
if h: h -= 1
if size: lcp[0] = 0
return sa, lcp
def LRIHP1(h):
n = len(h); h.append(0)
stack = []; ans = len(s); i = 0
while i < n+1:
if not stack or h[stack[-1]] <= h[i]:
stack.append(i); i+= 1; continue
top = stack.pop()
left = i-stack[-1] if stack else i+1
ans = max(ans, h[top]*left)
h.pop()
return ans
s = input()
sa, lcp = LCPArray(s)
print(LRIHP1(lcp))
Python 2 String Function Calculation HackerRank Solution
#!/usr/bin/python
def suffix_array(line):
isa, sa, lb = [0] * len(line), [0] * len(line), [0] * len(line)
for i in xrange(len(line)): sa[i] = ord(line[i])
size = 1
while size <= len(line):
for i in xrange(len(lb)):
if i + size < len(line): lb[i] = ((sa[i], sa[i + size]), i)
else: lb[i] = ((sa[i], -1), i)
lb.sort()
sa[lb[0][1]] = 0
for i in xrange(1, len(lb)):
cls, idx = lb[i]
if cls == lb[i - 1][0]: sa[idx] = sa[lb[i - 1][1]]
else: sa[idx] = sa[lb[i - 1][1]] + 1
size *= 2
for i, p in enumerate(sa): isa[p] = i
return isa, sa
def lcp(line, sa, rank):
lcp = [0] * len(sa)
h = 0
for i in xrange(len(line)):
if rank[i] == 0:
continue
j = sa[rank[i] - 1]
while line[i + h] == line[j + h]: h += 1
lcp[rank[i]] = h
if h > 0: h -= 1
return lcp
def solve1(line):
line = line + chr(0)
sa, rank = suffix_array(line)
lp = lcp(line, sa, rank)
lp.append(0)
ans, st = len(line) - 1, []
suffix, length, count = 0, len(line) - 1, 1
for i, l in enumerate(lp):
pos = i
while st and st[-1][1] > l:
j, h = st.pop()
pos = j
if (i - j + 1) * h > ans:
ans = (i - j + 1) * h
suffix, length, count = sa[j - 1], h, i - j + 1
if not st or st[-1][1] < l:
st.append((pos, l))
#print sa
#print lp
#print 'Sub[{}:{}] count={}'.format(suffix, suffix + length, count)
#print line[suffix:suffix + length]
return ans
def solve2(line):
class Substr:
def __init__(self, line, i, j):
self.line = line
self.b = i
self.e = j
self._hash = hash(line[i:j])
def __hash__(self):
return self._hash
def __eq__(self, other):
if hash(self) != hash(other):
return False
return self.line[self.b:self.e] == other.line[other.b:other.e]
def __ne__(self, other):
if hash(self) != hash(other):
return True
return self.line[self.b:self.e] != other.line[other.b:other.e]
def __len__(self):
return self.e - self.b
subs = {}
ans = len(line)
suffix, length, count = 0, len(line), 1
for i in xrange(len(line)):
for j in xrange(i + 1, len(line) + 1):
sub = Substr(line, i, j)
occ = subs.get(sub, 0) + 1
subs[sub] = occ
if occ * len(sub) > ans:
ans = occ * len(sub)
suffix, length, count = i, j - i, occ
print 'Sub[{}:{}] count={}'.format(suffix, suffix + length, count)
print line[suffix:suffix + length]
return ans
def main():
line = raw_input()
print solve1(line)
#assert solve1(line) == solve2(line)
main()
C String Function Calculation HackerRank Solution
/*
aaaaaa
12
abcabcddd
9
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NN 100001
typedef struct _node{
int u;
int w;
} node;
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int size,int *heap_list);
int init( int n ,int *N,int *tree);
void range_increment( int i, int j, int val ,int N,int *tree);
int query( int i ,int N,int *tree);
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);
void merge(int*a,int*left,int*right,int left_size, int right_size);
void sort_a(int*a,int size);
void suffixSort(int n);
void LCP(int n);
char str[NN]; //input
int rank[NN], pos[NN], lcp[NN]; //output
int cnt[NN], next[NN]; //internal
int bh[NN], b2h[NN];
int main(){
scanf("%s",str);
int len,i,c=0,heap_size=0,group,N,diff,tmax;
int *index,*p,*u,*v,*ans,*tree;
node *heap,temp;
long long max=-1;
len=strlen(str);
suffixSort(len);
LCP(len);
index=(int*)malloc(len*sizeof(int));
p=(int*)malloc(len*sizeof(int));
u=(int*)malloc(len*sizeof(int));
v=(int*)malloc(len*sizeof(int));
ans=(int*)malloc(len*sizeof(int));
tree=(int*)malloc(3*len*sizeof(int));
heap=(node*)malloc(2*len*sizeof(node));
for(i=0;i<len;i++)
index[i]=i;
sort_a2(lcp,index,len);
u[0]=0;
v[0]=len-1;
temp.u=0;
temp.w=len;
c++;
init(len,&N,tree);
heap_insert(heap,&temp,&heap_size,p);
for(i=0;i<len;i++){
if(i && lcp[i]!=lcp[i-1])
ans[lcp[i-1]]=heap[1].w;
group=query(index[i]+1,N,tree);
temp.u=group;
temp.w=v[group]-index[i];
u[c]=u[group];
u[group]=index[i]+1;
heap_update(heap,&temp,heap_size,p);
if(index[i]!=u[c]){
v[c]=index[i]-1;
temp.u=c;
temp.w=index[i]-u[c];
heap_insert(heap,&temp,&heap_size,p);
diff=c-group;
range_increment(u[c]+1,v[c]+1,diff,N,tree);
c++;
}
}
ans[lcp[i-1]]=heap[1].w;
tmax=len-1;
for(i=0;i<len;i++)
if(ans[i]==-1)
ans[i]=tmax;
else
tmax=ans[i];
for(i=0;i<len;i++)
if(max==-1 || (ans[i]+1)*(long long)(i+1)>max)
max=(ans[i]+1)*(long long)(i+1);
printf("%lld",max);
return 0;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w>heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int size,int *heap_list){
int index=heap_list[elem->u];
int max,maxi;
while(1){
if(2*index<=size){
max=heap[2*index].w;
maxi=2*index;
}
else
break;
if(2*index+1<=size && heap[2*index+1].w>max){
max=heap[2*index+1].w;
maxi=2*index+1;
}
if(elem->w<max){
heap[index]=heap[maxi];
heap_list[heap[index].u]=index;
index=maxi;
}
else
break;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
// initialises a tree for n data entries
int init( int n ,int *N,int *tree)
{
(*N) = 1;
while( (*N) < n ) (*N) *= 2;
int i;
for( i = 1; i < (*N) + n; i++ ) tree[i] = 0;
return 0;
}
// increments a[k] by val for all k between i and j, inclusive
void range_increment( int i, int j, int val ,int N,int *tree)
{
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] += val;
if( j % 2 == 0 ) tree[j] += val;
}
}
// compute a[i]
int query( int i ,int N,int *tree)
{
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans += tree[j];
return ans;
}
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;
}
void merge(int*a,int*left,int*right,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[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (str[left[i]] <= str[right[j]]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void suffixSort(int n){
//sort suffixes according to their first characters
int h,i,j,k;
for (i=0; i<n; ++i){
pos[i] = i;
}
sort_a(pos, n);
//{pos contains the list of suffixes sorted by their first character}
for (i=0; i<n; ++i){
bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
b2h[i] = 0;
}
for (h = 1; h < n; h <<= 1){
//{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]}
int buckets = 0;
for (i=0; i < n; i = j){
j = i + 1;
while (j < n && !bh[j]) j++;
next[i] = j;
buckets++;
}
if (buckets == n) break; // We are done! Lucky bastards!
//{suffixes are separted in buckets containing strings starting with the same h characters}
for (i = 0; i < n; i = next[i]){
cnt[i] = 0;
for (j = i; j < next[i]; ++j){
rank[pos[j]] = i;
}
}
cnt[rank[n - h]]++;
b2h[rank[n - h]] = 1;
for (i = 0; i < n; i = next[i]){
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0){
int head = rank[s];
rank[s] = head + cnt[head]++;
b2h[rank[s]] = 1;
}
}
for (j = i; j < next[i]; ++j){
int s = pos[j] - h;
if (s >= 0 && b2h[rank[s]]){
for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0;
}
}
}
for (i=0; i<n; ++i){
pos[rank[i]] = i;
bh[i] |= b2h[i];
}
}
for (i=0; i<n; ++i){
rank[pos[i]] = i;
}
}
// End of suffix array algorithm
void LCP(int n){
int l=0,i,j,k;
for(i=0;i<n;i++){
k=rank[i];
if(!k)
continue;
j=pos[k-1];
while(str[i+l]==str[j+l])
l++;
lcp[k]=l;
if(l>0)
l--;
}
lcp[0]=0;
return;
}
