HackerRank Letter Islands Problem Solution Yashwant Parihar, May 2, 2023May 2, 2023 In this post, we will solve HackerRank Letter Islands Problem Solution. You are given string s and number k.Consider a substring p of string 8. For each position of string & mark it if there is an occurence of the substring that covers the position. More formally, position i will be marked if there exists such index j that: j ≤i≤ j + p-1 and 8j8j+1.8j+p-1 = p. We will tell p produce a islands if all the marked positions form a groups of contiguous positions.For example, if we have a string ababaewabaq the substring aba marks the positions 1, 2, 3, 4, 5, 8, 9, 10; that is XXXXXewXXXq (X denotes marked position). We can see 2 groups of contiguous positions, that is 2 islands. Finally, substring aba produces 2 islands in the stringababaewabaq.Calculate and print the number of different substrings of string $ that produce exactly k islands.Input FormatThe first line contains string 8 (1 ≤ |s| ≤ 105). The string consists of lowercase letters only. The second line contains an integer k (1 ≤ k ≤ |s|). Output Format Output a single integer the answer to the problem. Sample Input abaab 2 Sample Output 3 Explanation All the suitable substrings are: a, ab, b. HackerRank Letter Islands Problem Solution Letter Islands C Solution #include <stdio.h> #include <stdlib.h> #include <string.h> #define A_SIZE 26 #define MIN_C 'a' typedef struct _st_node st_node; typedef struct _st_edge st_edge; typedef enum _type{ ONE=1, TWO, BOTH } type; struct _st_node{ st_node *suffix_link; type t; st_edge *edges[A_SIZE+2]; }; struct _st_edge{ int from; int to; int suffix_index; st_node *node; }; typedef struct _ct_node{ int size; int priority; int value; struct _ct_node *left,*right; } ct_node; int sizeOf(ct_node *root); void recalc(ct_node *root); ct_node* merge(ct_node *L,ct_node *R); void split1(int x,ct_node **L,ct_node **R,ct_node *root); void split2(int x,ct_node **L,ct_node **R,ct_node *root); int max(ct_node *root); int min(ct_node *root); void insert(ct_node **root,ct_node *t); void delete(ct_node **root,int x); void full_insert(ct_node **arr,ct_node **diff,ct_node *t); void dfs_aux(ct_node **arr,ct_node **diff,ct_node *t); void dfs(st_node *root,int len_from, int len_to,int suffix_index,ct_node **arr,ct_node **diff); void suffix_tree(st_node *root, char *str,int len,int flag,int offset); int inter(int l1,int l2,int l3,int l4); char str[100001]; int k,len; long long ans; int main(){ st_node root; ct_node *r1,*r2; scanf("%s%d",str,&k); len=strlen(str); memset(&root,0,sizeof(st_node)); suffix_tree(&root,str,len,0,0); dfs(&root,0,0,0,&r1,&r2); printf("%lld",ans); return 0; } int sizeOf(ct_node *root){ return (root)?root->size:0; } void recalc(ct_node *root){ root->size=sizeOf(root->left)+ sizeOf(root->right)+1; return; } ct_node* merge(ct_node *L,ct_node *R){ if(!L) return R; if(!R) return L; if(L->priority>R->priority){ L->right=merge(L->right,R); recalc(L); return L; } R->left=merge(L,R->left); recalc(R); return R; } void split1(int x,ct_node **L, ct_node **R,ct_node *root){ if(!root){ *L=*R=NULL; return; } int curIndex=sizeOf(root->left); ct_node *t; if(curIndex<=x){ split1(x-curIndex-1,&t,R,root->right); root->right=t; recalc(root); *L=root; } else{ split1(x,L,&t,root->left); root->left=t; recalc(root); *R=root; } return; } void split2(int x,ct_node **L, ct_node **R,ct_node *root){ if(!root){ *L=*R=NULL; return; } int curIndex=root->value; ct_node *t; if(curIndex<=x){ split2(x,&t,R,root->right); root->right=t; recalc(root); *L=root; } else{ split2(x,L,&t,root->left); root->left=t; recalc(root); *R=root; } return; } int max(ct_node *root){ if(root->right) return max(root->right); return root->value; } int min(ct_node *root){ if(root->left) return min(root->left); return root->value; } void insert(ct_node **root,ct_node *t){ ct_node *t1,*t2; split2(t->value,&t1,&t2,*root); *root=merge(t1,merge(t,t2)); return; } void delete(ct_node **root,int x){ ct_node *t1,*t2,*t3; split2(x,&t1,&t3,*root); split1(sizeOf(t1)-2,&t1,&t2,t1); *root=merge(t1,t3); return; } void full_insert(ct_node **arr, ct_node **diff,ct_node *t){ int v1,v2; ct_node *t1,*t2,*t3; split2(t->value,&t1,&t2,*arr); if(!t1 && !t2) *diff=NULL; else if(!t1){ v1=min(t2)-t->value; t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } else if(!t2){ v1=t->value-max(t1); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } else{ v1=max(t1); v2=min(t2); delete(diff,v2-v1); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=t->value-v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v2-t->value; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } *arr=merge(t1,merge(t,t2)); return; } void dfs_aux(ct_node **arr, ct_node **diff,ct_node *t){ if(!t) return; dfs_aux(arr,diff,t->left); dfs_aux(arr,diff,t->right); t->size=1; t->left=t->right=NULL; full_insert(arr,diff,t); return; } void dfs(st_node *root,int len_from, int len_to,int suffix_index, ct_node **arr,ct_node **diff){ int v1,v2,i; ct_node *p_arr,*p_diff,*pp_arr,*pp_diff,*t1,*t2; if(!root){ p_arr=(ct_node*)malloc(sizeof(ct_node)); p_arr->priority=rand(); p_arr->value=suffix_index; p_arr->size=1; p_arr->left=p_arr->right=NULL; *arr=p_arr; *diff=NULL; return; } p_arr=p_diff=NULL; if(root->edges[A_SIZE]){ dfs(root->edges[A_SIZE]->node,0,0, root->edges[A_SIZE]->suffix_index, &pp_arr,&pp_diff); if(sizeOf(p_arr)<sizeOf(pp_arr)){ dfs_aux(&pp_arr,&pp_diff,p_arr); p_arr=pp_arr; p_diff=pp_diff; } else dfs_aux(&p_arr,&p_diff,pp_arr); } for(i=0;i<A_SIZE;i++) if(root->edges[i]){ dfs(root->edges[i]->node,len_to+1, len_to+root->edges[i]->to-root->edges[i]->from+1, root->edges[i]->suffix_index,&pp_arr,&pp_diff); if(sizeOf(p_arr)<sizeOf(pp_arr)){ dfs_aux(&pp_arr,&pp_diff,p_arr); p_arr=pp_arr; p_diff=pp_diff; } else dfs_aux(&p_arr,&p_diff,pp_arr); } *arr=p_arr; *diff=p_diff; if(len_to){ if(sizeOf(p_arr)<k) return; split1(sizeOf(p_arr)-k-1,&t1,&t2,p_diff); if(!t1 && !t2) ans+=inter(0,100000,len_from,len_to); else if(!t1) ans+=inter(0,min(t2)-1,len_from,len_to); else if(!t2) ans+=inter(max(t1),100000,len_from,len_to); else{ v1=max(t1); v2=min(t2); if(v1!=v2) ans+=inter(v1,v2-1,len_from,len_to); } p_diff=merge(t1,t2); } return; } void suffix_tree(st_node *root, char *str,int len,int flag,int offset){ int a_edge,a_len=0,remainder=0, need_insert,from,max,i; type t; st_node *a_node=root,*pre_node,*t_node,*tt_node,*pp_node=NULL; st_edge *t_edge; if(flag){ max=A_SIZE+1; t=TWO; } else{ max=A_SIZE; t=ONE; } root->t|=t; for(i=offset;i<=offset+len;i++){ need_insert=0; pre_node=NULL; remainder++; if(i==offset+len) need_insert=1; else if(a_len) if(str[a_node->edges[a_edge]->from+a_len]==str[i]) if(a_node->edges[a_edge]->from+ a_len==a_node->edges[a_edge]->to){ a_node=a_node->edges[a_edge]->node; a_node->t|=t; a_len=0; } else a_len++; else need_insert=1; else if(a_node->edges[str[i]-MIN_C]) if(a_node->edges[str[i]-MIN_C]->from== a_node->edges[str[i]-MIN_C]->to){ a_node=a_node->edges[str[i]-MIN_C]->node; a_node->t|=t; } else{ a_edge=str[i]-MIN_C; a_len=1; } else need_insert=1; if(need_insert) for(;remainder>0;remainder--){ if(!a_len) if(i==offset+len){ a_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); a_node->edges[max]->suffix_index=i-remainder+1; a_node->edges[max]->node=NULL; t_node=tt_node=a_node; } else{ if(a_node->edges[str[i]-MIN_C]){ if(pre_node) pre_node->suffix_link=a_node; if(a_node->edges[ str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to){ a_node=a_node->edges[str[i]-MIN_C]->node; a_node->t|=t; } else{ a_edge=str[i]-MIN_C; a_len=1; } break; } t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=i; t_edge->to=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; a_node->edges[str[i]-MIN_C]=t_edge; t_node=a_node; tt_node=t_edge->node; } else{ if(i!=offset+len && str[ a_node->edges[a_edge]->from+a_len]==str[i]){ if(pre_node) pre_node->suffix_link=a_node; if(a_node->edges[a_edge]->from+ a_len==a_node->edges[a_edge]->to){ a_node=a_node->edges[a_edge]->node; a_node->t|=t; a_len=0; } else a_len++; break; } t_node=(st_node*)malloc(sizeof(st_node)); memset(t_node,0,sizeof(st_node)); t_node->t|=(a_node->edges[a_edge]->node->t|t); t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=a_node->edges[a_edge]->from+a_len; t_edge->to=a_node->edges[a_edge]->to; t_edge->suffix_index=a_node->edges[a_edge]->suffix_index; t_edge->node=a_node->edges[a_edge]->node; from=a_node->edges[a_edge]->from; a_node->edges[a_edge]->node=t_node; a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1; t_node->edges[str[t_edge->from]-MIN_C]=t_edge; if(i==offset+len){ t_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_node->edges[max]->suffix_index=i-remainder+1; t_node->edges[max]->node=NULL; tt_node=t_node; } else{ t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=i; t_edge->to=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; t_node->edges[str[i]-MIN_C]=t_edge; tt_node=t_edge->node; } } if(pre_node) pre_node->suffix_link=t_node; pre_node=t_node; if(pp_node) pp_node->suffix_link=tt_node; pp_node=tt_node; if(a_node==root && a_len>0){ if(remainder>1) a_edge=str[i-remainder+2]-MIN_C; from=i-remainder+2; a_len--; } else if(a_node!=root) if(a_node->suffix_link){ a_node=a_node->suffix_link; a_node->t|=t; } else a_node=root; while(a_len>0 && a_len>=a_node->edges[ a_edge]->to-a_node->edges[a_edge]->from+1){ a_len-=a_node->edges[ a_edge]->to-a_node->edges[a_edge]->from+1; from+=a_node->edges[ a_edge]->to-a_node->edges[a_edge]->from+1; a_node=a_node->edges[ a_edge]->node; a_node->t|=t; a_edge=str[from]-MIN_C; } } } return; } int inter(int l1,int l2,int l3,int l4){ if(l3>l2 || l1>l4) return 0; if(l3>=l1) if(l4>=l2) return l2-l3+1; else return l4-l3+1; else if(l4>=l2) return l2-l1+1; else return l4-l1+1; } Letter Islands C++ Solution #include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <map> #include <set> #include <stack> #include <utility> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++) #define ROF(i, a, b) for (int i = (b); --i >= (a); ) struct Pos { static int id; set<int> a; tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> d; int countLT(int key) { return d.order_of_key(pii(key, 0)); } size_t size() { return a.size(); } void insert(int i) { a.insert(i); auto it = a.lower_bound(i); auto prev = it, next = it; if (it != a.begin()) --prev; if (it != a.end()) ++next; if (it != prev) { d.insert(pii{*it-*prev, id++}); if (it != next && next != a.end()) d.erase(d.lower_bound(pii{*next-*prev, 0})); } if (it != next && next != a.end()) d.insert(pii{*next-*it, id++}); } void join(Pos &b) { for (int x: b.a) insert(x); } Pos() = default; Pos(Pos &&b) { a.swap(b.a); d.swap(b.d); } Pos &operator=(Pos &&b) noexcept { a.swap(b.a); d.swap(b.d); return *this; } }; int Pos::id = 0, n, k; ll ans; namespace KoAluru { bool *t; int *b; template<typename T> void bucket(T a[], int n, int k, bool end) { fill_n(b, k, 0); REP(i, n) b[a[i]]++; if (end) FOR(i, 1, k) b[i] += b[i-1]; else { int s = 0; REP(i, k) s += b[i], b[i] = s-b[i]; } } template<typename T> void plus_to_minus(T a[], int sa[], int n, int k) { bucket(a, n, k, false); sa[b[a[n-1]]++] = n-1; REP(i, n-1) { int j = sa[i]-1; if (j >= 0 && ! t[j]) sa[b[a[j]]++] = j; } } template<typename T> void minus_to_plus(T a[], int sa[], int n, int k) { bucket(a, n, k, true); ROF(i, 0, n) { int j = sa[i]-1; if (j >= 0 && t[j]) sa[--b[a[j]]] = j; } } template<typename T> void ka(T a[], int sa[], int n, int k) { t[n-1] = false; ROF(i, 0, n-1) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; bool minor = 2 * count(t, t+n, false) > n; bucket(a, n, k, minor); fill_n(sa, n, -1); if (minor) { REP(i, n) if (t[i]) sa[--b[a[i]]] = i; plus_to_minus(a, sa, n, k); minus_to_plus(a, sa, n, k); } else { sa[b[a[n-1]]++] = n-1; REP(i, n-1) if (! t[i]) sa[b[a[i]]++] = i; minus_to_plus(a, sa, n, k); plus_to_minus(a, sa, n, k); } int last = -1, name = 0, nn = count(t, t+n, minor); int *sa2, *pi; if (minor) sa2 = sa, pi = sa+n-nn; else sa2 = sa+n-nn, pi = sa; fill_n(b, n, -1); REP(i, n) if (sa[i] >= 0 && minor == t[sa[i]]) { bool diff = last == -1; int p = sa[i]; if (! diff) REP(j, n) { if (last+j >= n || p+j >= n || a[last+j] != a[p+j] || t[last+j] != t[p+j]) { diff = true; break; } else if (j > 0 && (minor == t[last+j] || minor == t[p+j])) break; } if (diff) { name++; last = p; } b[p] = name-1; } nn = 0; REP(i, n) if (b[i] >= 0) pi[nn++] = b[i]; if (name < nn) ka(pi, sa2, nn, name); else REP(i, nn) sa2[pi[i]] = i; ROF(i, 0, nn) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; nn = 0; bucket(a, n, k, minor); if (minor) { REP(i, n) if (minor == t[i]) pi[nn++] = i; REP(i, nn) sa[i] = pi[sa2[i]]; ROF(i, 0, nn) { int j = sa[i]; sa[i] = -1; sa[--b[a[j]]] = j; } } else { REP(i, n) if (minor == t[i]) pi[nn++] = i; ROF(i, 0, nn) sa[n-nn+i] = pi[sa2[i]]; REP(i, nn) { int j = sa[n-nn+i]; sa[n-nn+i] = -1; sa[b[a[j]]++] = j; } } if (minor) plus_to_minus(a, sa, n, k); else minus_to_plus(a, sa, n, k); } template<typename T> void main(T a[], int sa[], int b[], int n, int k) { if (n > 0) { KoAluru::b = b; t = new bool[n]; ka(a, sa, n, k); delete[] t; } } template<typename T> void calc_rank_lcp(T a[], int sa[], int n, int rank[], int lcp[]) { REP(i, n) rank[sa[i]] = i; int k = 0; lcp[0] = 0; FOR(i, 0, n) if (rank[i]) { for (int j = sa[rank[i]-1]; i+k < n && j+k < n && a[i+k] == a[j+k]; k++); lcp[rank[i]] = k; k && k--; } } void calc_child(int lcp[], int n, int child[]) { stack<int> st; st.push(0); int last = -1; fill_n(child, n, -1); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) { last = st.top(); st.pop(); if (lcp[i] <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } if (last != -1) { child[i-1] = last; last = -1; } st.push(i); } while (0 < lcp[st.top()]) { last = st.top(); st.pop(); if (0 <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } while (! st.empty()) st.pop(); st.push(0); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) st.pop(); if (lcp[i] == lcp[st.top()]) { child[st.top()] = i; st.pop(); } st.push(i); } } void top_down(int sa[], int lcp[], int child[], int l, int h, int ht, Pos &data) { int ht2; if (l == h-1) { ht2 = n-sa[l]; data.insert(sa[l]); } else { int i = l < child[h-1] && child[h-1] < h ? child[h-1] : child[l]; ht2 = lcp[i]; { Pos cur; top_down(sa, lcp, child, l, i, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } for (; child[i] > i && lcp[child[i]] == lcp[i]; i = child[i]) { Pos cur; top_down(sa, lcp, child, i, child[i], ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } { Pos cur; top_down(sa, lcp, child, i, h, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } } l = ht+1; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k < data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } int from = l; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k <= data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } ans += l-from; } }; const int N = 100000; char a[N+1]; int b[N], sa[N], rnk[N], lcp[N], child[N]; int main() { scanf("%s%d", a, &k); n = strlen(a); KoAluru::main(a, sa, b, n, 127); KoAluru::calc_rank_lcp(a, sa, n, rnk, lcp); KoAluru::calc_child(lcp, n, child); Pos data; KoAluru::top_down(sa, lcp, child, 0, n, 0, data); printf("%lld\n", ans); } Letter Islands C# Solution using System; using System.Collections.Generic; using System.IO; class Solution { static void Main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */ var text = Console.ReadLine(); var target = int.Parse(Console.ReadLine()); var result = new Solution().CountSubstrings(text, target); Console.WriteLine(result); } int tt_n; int[] tt_sv; int[] sp_ss; int[] sn_ss; int[] ip_ss; int[] in_ss; int[] ao_is; int[] ao_in; RangeMinimumQuery ao_iin; int[] ae_is; int ad_n; int[] ad_in; int vv_n; int[] vv_vn; int cc_n; int[] co_cn; int[] ch_cs; int[] cb_ci; int[] ce_ci; // Basic algorithm. // // Incrementally split string into cells containing equal substrings of length L. (L = 0, 1, 2, 3, ...) // For each cell count the number of islands its substrings generate. If this number equals the target k // increment the result. // // Optimizations. // // Precompute suffix array (SA), longest common prefix (LCP) array and range minimum query (RMQ) array of LCP. // Use binary search on SA to get the lengths of cells, which the current cell splits into. // Use RMQ of LCP to get the lengths of the common prefixes of arbitrary substrings. // // If the cell contains only one substring and the target k = 1, update the result by the number of substrings // that can be generated form the current by incrementing its length plus 1 for the substring itself // ~(string length - substring length). // If the cell contains fewer substrings then the target k, skip it. // If the cell splits into one big cell and some smaller ones, instead of creating all cells lineary, // create only smaller ones. // To get the big cell, remove the smaller ones from the initial cell. To count islands in the resulting big // cell, maintain // doubly linked lists of the beginings of its substrings (SL) and potential islands (IL). SL must be ordered. // This way, when the islands of the big cell are counted, it is only necessary to go through IL but not SL. // To avoid the situation, when substrings of a cell increase in length without splitting it, increase their // length up to the length of their LCP. To do it, first sort distances between islands. Then incrementally // remove islands with the same distances, checking if the resulting number of islands equals the target k. // If it is, update the result by the number of substrings that can be generated form the current by // incrementing its length up to the point, when the number of islands becomes smaller then the target k // ~(Min(LCP, next distance) - current distance). long CountSubstrings(string text, int target) { if (text == null || text.Length < 1 || target < 1) { throw new ArgumentException(); } var result = 0L; tt_n = text.Length; tt_sv = new int[tt_n]; sp_ss = new int[tt_n]; sn_ss = new int[tt_n]; ip_ss = new int[tt_n]; in_ss = new int[tt_n]; ao_is = new int[tt_n]; ao_in = new int[tt_n]; ae_is = new int[tt_n]; ad_in = new int[tt_n]; vv_n = 28; vv_vn = new int[vv_n]; cc_n = 0; co_cn = new int[tt_n]; ch_cs = new int[tt_n]; cb_ci = new int[tt_n]; ce_ci = new int[tt_n]; for (var s = 0; s < tt_n; ++s) { tt_sv[s] = (int)text[s] - (int)'a'; } ListNode.Link(0, sp_ss, sn_ss); ListNode.Link(0, ip_ss, in_ss); for (var s = 1; s < tt_n; ++s) { ListNode.LinkBefore(s, 0, sp_ss, sn_ss); ListNode.Initialize(s, ip_ss, in_ss); } SuffixSort.Solve(tt_sv, ao_is); LongestCommonPrefix.Solve(tt_sv, ao_is, ao_in); ao_iin = new RangeMinimumQuery(ao_in); co_cn[0] = 0; ch_cs[0] = 0; cb_ci[0] = 0; ce_ci[0] = tt_n; ++cc_n; while (cc_n > 0) { --cc_n; var co_n = co_cn[cc_n]; var ch_s = ch_cs[cc_n]; var cb_i = cb_ci[cc_n]; var ce_i = ce_ci[cc_n]; for (var v = 0; v < vv_n; ++v) { vv_vn[v] = 0; } var s_f = false; var m_v = 0; { var i = cb_i; var s = ao_is[i]; if (s + co_n == tt_n) { vv_vn[1] = 1; ++i; } while (i < ce_i) { var v = tt_sv[ao_is[i] + co_n]; var n = BinarySearch.Solve(o => tt_sv[ao_is[i + o] + co_n] - (v + 1), ce_i - i); if (n < 0) { n = ~n; } vv_vn[v + 2] = n; i += n; } } { var s_n = 0; for (var v = 0; v < vv_n; ++v) { var n = vv_vn[v]; if (n > 0) { if (vv_vn[m_v] < n) { m_v = v; } s_n += n * (int)Math.Ceiling(Math.Log(n, 2)); } } s_n -= vv_vn[m_v] * (int)Math.Ceiling(Math.Log(vv_vn[m_v], 2)); s_f = (ce_i - cb_i < s_n); } for (var v = 1; v < vv_n; ++v) { vv_vn[v] += vv_vn[v - 1]; } if (s_f) // balanced split { { var s = ch_s; do { var v = (s + co_n < tt_n) ? tt_sv[s + co_n] : -1; ae_is[vv_vn[v + 1]++] = s; s = sn_ss[s]; } while (s != ch_s); } { var n = 0; for (var v = 0; v < vv_n; ++v) { if (vv_vn[v] != n) { var n_n = vv_vn[v]; vv_vn[v] = n; n = n_n; } } } { if (vv_vn[1] == 1) { ListNode.Initialize(ae_is[0], sp_ss, sn_ss); ListNode.Initialize(ae_is[0], ip_ss, in_ss); } for (var v = 2; v < vv_n; ++v) { var i = vv_vn[v - 1]; var n_i = vv_vn[v]; var n = n_i - i; if (n < target) { for (; i < n_i; ++i) { var s = ae_is[i]; ListNode.Initialize(s, sp_ss, sn_ss); ListNode.Initialize(s, ip_ss, in_ss); } } else if (n == 1) { var s = ae_is[i]; ListNode.Initialize(s, sp_ss, sn_ss); ListNode.Initialize(s, ip_ss, in_ss); result += tt_n - (s + co_n); } else { AddCell(cb_i, i, n, co_n, target, ref result); } } } } else // unbalanced split { if (vv_vn[1] == 1) { RemoveSuffix(ao_is[cb_i], ref ch_s); } for (var v = 2; v < vv_n; ++v) { var i = cb_i + vv_vn[v - 1]; var n_i = cb_i + vv_vn[v]; var n = n_i - i; if (n < target) { for (; i < n_i; ++i) { RemoveSuffix(ao_is[i], ref ch_s); } } else if (n == 1) { RemoveSuffix(ao_is[i], ref ch_s); result += tt_n - (ao_is[i] + co_n); } else if (v != m_v) { Array.Copy(ao_is, i, ae_is, 0, n); Array.Sort(ae_is, 0, n); for (var s_i = 0; s_i < n; ++s_i) { RemoveSuffix(ae_is[s_i], ref ch_s); } AddCell(i, 0, n, co_n, target, ref result); } } if (ch_s != -1) { AddBigCell(ch_s, cb_i + vv_vn[m_v - 1], cb_i + vv_vn[m_v], co_n, target, ref result); } } } return result; } void RemoveSuffix(int s, ref int ch_s) { var n_s = sn_ss[s]; ListNode.Unlink(s, sp_ss, sn_ss); if (s == n_s) { ListNode.Initialize(s, ip_ss, in_ss); ch_s = -1; } else { if (!ListNode.IsLinked(n_s, in_ss)) { ListNode.LinkBefore(n_s, ch_s, ip_ss, in_ss); } if (ListNode.IsLinked(s, in_ss)) { ListNode.Unlink(s, ip_ss, in_ss); } if (ch_s == s) { ch_s = n_s; } } } void AddCell(int b_i, int e_i, int e_n, int co_n, int target, ref long result) { var ch_s = ae_is[e_i]; var cb_i = b_i + e_i; var ce_i = b_i + e_i + e_n; var i_n = 1; var p_n = ao_iin.Minimum(cb_i + 1, ce_i - cb_i - 1); var s_f = (p_n > co_n + 1); ad_n = 0; co_cn[cc_n] = p_n; ch_cs[cc_n] = ch_s; cb_ci[cc_n] = cb_i; ce_ci[cc_n] = ce_i; ++cc_n; ListNode.Link(ch_s, sp_ss, sn_ss); ListNode.Link(ch_s, ip_ss, in_ss); for (var i = 1; i < e_n; ++i) { var s = ae_is[e_i + i]; ListNode.LinkBefore(s, ch_s, sp_ss, sn_ss); if (s - sp_ss[s] > co_n + 1) { ad_in[ad_n++] = s - sp_ss[s]; ++i_n; ListNode.LinkBefore(s, ch_s, ip_ss, in_ss); } else { ListNode.Initialize(s, ip_ss, in_ss); } } if (s_f) { SkipCommonPrefix(i_n, co_n, p_n, target, ref result); } else if (i_n == target) { ++result; } } void AddBigCell(int ch_s, int cb_i, int ce_i, int co_n, int target, ref long result) { var i_n = 1; var p_n = ao_iin.Minimum(cb_i + 1, ce_i - cb_i - 1); var s_f = (p_n > co_n + 1); ad_n = 0; co_cn[cc_n] = p_n; ch_cs[cc_n] = ch_s; cb_ci[cc_n] = cb_i; ce_ci[cc_n] = ce_i; ++cc_n; for (var s = in_ss[ch_s]; s != ch_s; ) { var n_s = in_ss[s]; if (s - sp_ss[s] > co_n + 1) { ++i_n; if (s_f) { ad_in[ad_n++] = s - sp_ss[s]; } else if (i_n > target) { break; } } else { ListNode.Unlink(s, ip_ss, in_ss); } s = n_s; } if (s_f) { SkipCommonPrefix(i_n, co_n, p_n, target, ref result); } else if (i_n == target) { ++result; } } void SkipCommonPrefix(int i_n, int co_n, int p_n, int target, ref long result) { Array.Sort(ad_in, 0, ad_n); var b_n = (i_n == target) ? (co_n + 1) - 1 : -1; var e_n = p_n; for (var i = 0; i < ad_n; ) { var d_n = ad_in[i]; if (d_n > p_n) { break; } for (; i < ad_n && ad_in[i] == d_n; ++i, --i_n) ; if (i_n == target) { b_n = d_n - 1; } if (i_n < target) { e_n = d_n - 1; break; } } if (b_n != -1) { result += e_n - b_n; } } public static class ListNode { public static void Initialize(int node, int[] previous, int[] next) { previous[node] = -1; next[node] = -1; } public static bool IsLinked(int node, int[] next) { return (next[node] != -1); } public static void Link(int unlinked, int[] previous, int[] next) { previous[unlinked] = unlinked; next[unlinked] = unlinked; } public static void LinkBefore(int unlinked, int linked, int[] previous, int[] next) { previous[unlinked] = previous[linked]; next[unlinked] = linked; next[previous[linked]] = unlinked; previous[linked] = unlinked; } public static void LinkAfter(int unlinked, int linked, int[] previous, int[] next) { previous[unlinked] = linked; next[unlinked] = next[linked]; previous[next[linked]] = unlinked; next[linked] = unlinked; } public static void Unlink(int linked, int[] previous, int[] next) { next[previous[linked]] = next[linked]; previous[next[linked]] = previous[linked]; previous[linked] = -1; next[linked] = -1; } } public static class BinarySearch { public static int Solve(Func<int, int> compare, int range) { if (compare == null || range < 0) { throw new ArgumentException(); } var begin = 0; var end = range; while (begin < end) { var i = (begin + end) / 2; if (compare(i) < 0) { begin = i + 1; } else { end = i; } } return (end < range && compare(end) == 0) ? end : ~end; } } public class SuffixSort { public static void Solve(int[] text, int[] suffixes) { if (text == null || suffixes == null || text.Length > suffixes.Length) { throw new ArgumentException(); } if (text.Length > 0) { var ao_su = text; var aa_n = ao_su.Length; var aa_is = suffixes; var aa_iu = new int[aa_n]; var aa_su = new int[aa_n]; var as_n = 1; Comparison<int> compare = (a_s, b_s) => { if (aa_su[a_s] != aa_su[b_s]) { return aa_su[a_s] - aa_su[b_s]; } a_s += as_n; b_s += as_n; return (a_s < aa_n && b_s < aa_n) ? aa_su[a_s] - aa_su[b_s] : b_s - a_s; }; for (var i = 0; i < aa_n; ++i) { aa_is[i] = i; aa_su[i] = ao_su[i]; } for (;; as_n *= 2) { Array.Sort(aa_is, compare); for (var i = 1; i < aa_n; ++i) { aa_iu[i] = aa_iu[i - 1] + ((compare(aa_is[i], aa_is[i - 1]) > 0) ? 1 : 0); } if (aa_iu[aa_n - 1] == aa_n - 1) { break; } for (var i = 0; i < aa_n; ++i) { aa_su[aa_is[i]] = aa_iu[i]; } } } } } public class LongestCommonPrefix { public static void Solve(int[] text, int[] suffixes, int[] lcp) { if (text == null || suffixes == null || lcp == null || text.Length > suffixes.Length || text.Length > lcp.Length) { throw new ArgumentException(); } if (text.Length > 0) { var ao_su = text; var aa_n = ao_su.Length; var aa_is = suffixes; var aa_in = lcp; var aa_si = new int[aa_n]; for (var i = 0; i < aa_n; ++i) { aa_si[aa_is[i]] = i; } aa_in[0] = -1; for (int s = 0, n = 0; s < aa_n; ++s) { if (aa_si[s] != 0) { var p_s = aa_is[aa_si[s] - 1]; for (; p_s + n < aa_n && s + n < aa_n && ao_su[p_s + n] == ao_su[s + n]; ++n) ; aa_in[aa_si[s]] = n; if (n > 0) { --n; } } } } } } public class RangeMinimumQuery { public RangeMinimumQuery(int[] items) { if (items == null || items.Length == 0) { throw new Exception(); } var o_in = items; var o_n = o_in.Length; var r_n = 1; for (var n = o_n; (n >>= 1) > 0; ++r_n) ; aa_n = o_n; aa_in = new int[aa_n * r_n]; for (var i = 0; i < aa_n; ++i) { aa_in[i] = o_in[i]; } for (var r_i = 1; r_i < r_n; ++r_i) { for (var a_i = 0; a_i < aa_n - (1 << r_i) + 1; ++a_i) { aa_in[r_i * aa_n + a_i] = Math.Min(aa_in[(r_i - 1) * aa_n + a_i], aa_in[(r_i - 1) * aa_n + a_i + (1 << (r_i - 1))]); } } } public int Minimum(int index, int count) { if (index < 0 || count <= 0 || index + count > aa_n) { throw new Exception(); } var a_i = index; var a_n = count; var r_i = 0; for (var n = a_n; (n >>= 1) > 0; ++r_i) ; return Math.Min(aa_in[r_i * aa_n + a_i], aa_in[r_i * aa_n + a_i + a_n - (1 << r_i)]); } int aa_n; int[] aa_in; } } Letter Islands Java Solution import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); if(in.hasNext()){ final char[] str = in.next().toCharArray(); if(str.length>0 && in.hasNext()){ int k = in.nextInt(); if(k>0 && k<=str.length){ System.out.println(( new FoundSubStrings(str, k)).count()); } } } } static class FoundSubStrings { private final char[] str; private final int k; private Map<Long, SubString> curr; private Map<Long, SubString> next; private SubString previousSub=null; private int previousSubParentStartIndex = -1; private int previousSubLen = -1; public FoundSubStrings(char[] str, int k) { this.str = str; this.k = k; curr = new HashMap<>(str.length>32 ? str.length>>1 : str.length); next = new HashMap<>(str.length>32 ? str.length>>1 : str.length); } public long count(){ long countResult = 0; int startIndex; char lastChar = str[0]; int lastCharCount = 0; for(int i=0; i<=str.length; i++){ if(i==str.length || lastChar!=str[i]){ if(lastCharCount>1){ for(int j=i-lastCharCount; j<i-1; j++){ this.add(j, lastChar, i-j); } } this.add(i-1, lastChar); if(i!=str.length){ lastChar = str[i]; lastCharCount = 1; } } else { lastCharCount++; } } // this.switchLists(); // while(!curr.isEmpty()){ for(SubString subStr : curr.values()){ if(subStr.islands==k){ countResult++; if(k==1 && subStr.size==1){ countResult+=str.length-subStr.startIndex-subStr.len; continue; } } else if(subStr.size<k){ continue; } for(int i=0; i<subStr.size && ( (startIndex=subStr.indexes[i])<(str.length-subStr.len)); i++){ this.add(subStr.startIndex, startIndex, str[startIndex+subStr.len], subStr.len+1, subStr.size); } } this.switchLists(); } return countResult; } private void add(int parentStartIndex, int startIndex, char chr, int len, int childsLength){ if(previousSubParentStartIndex!=parentStartIndex || previousSubLen!=len || previousSub.chr!=chr){ long key = getKey(parentStartIndex, len, chr); previousSub = next.get(key); if(previousSub==null){ previousSub = new SubString(parentStartIndex, startIndex, chr, len, childsLength); next.put(key, previousSub); } previousSubParentStartIndex = previousSub.parentStartIndex; previousSubLen = len; } previousSub.addIndex(startIndex); } private void add(int startIndex, char chr, int len){ long key = getKey(len, chr); SubString sub = next.get(key); if(sub==null){ sub = new SubString(startIndex, chr, len); next.put(key, sub); } sub.addIndex(startIndex); } private void add(int startIndex, char chr){ if(previousSub==null || previousSubLen!=1 || previousSub.chr!=chr){ long key = getKey(chr); previousSub = next.get(key); if(previousSub==null){ previousSub = new SubString(startIndex, chr, 1); next.put(key, previousSub); } previousSubLen = 1; } previousSub.addIndex(startIndex); } private void switchLists(){ previousSubParentStartIndex = -1; previousSub = null; Map<Long, SubString> tmp = curr; curr = next; next = tmp; tmp.clear(); } public static long getKey(int parentStartIndex, int length, char chr){ return (((long)parentStartIndex) | (( long)length<<31) | ((long)chr)<<23); } public static long getKey(int length, char chr){ return (((long)length<<31) | (((long)chr)<<23)); } public static long getKey(char chr){ return (((long)chr)<<23); } class SubString implements Comparable<SubString> { private final int parentStartIndex; private final int len; private final char chr; private int startIndex; private int islands = 0; // private int[] indexes; private int size = 0; public SubString(int startIndex, char chr, int length) { this(-1, startIndex, chr, length, 16); } public SubString(int startIndex, char chr, int length, int childsLength) { this(-1, startIndex, chr, length, childsLength); } public SubString(int parentStartIndex, int startIndex, char chr, int length, int childsLength) { this.parentStartIndex = parentStartIndex; this.startIndex = startIndex; this.len = length; this.chr = chr; this.indexes = new int[ childsLength>16? 16: childsLength+1]; } public void addIndex(int index){ if(size==0 || (indexes[size-1]+len<index)){ islands++; } if(indexes.length==size+1){ int[] tmpArr = new int[indexes.length<<1]; System.arraycopy(indexes, 0, tmpArr, 0, indexes.length); indexes = tmpArr; } indexes[size++] = index; } @Override public int compareTo(SubString o) { return ( this.parentStartIndex==o.parentStartIndex) ? chr - o.chr : this.parentStartIndex - o.parentStartIndex; } @Override public String toString() { StringBuilder sb = new StringBuilder(100); sb.append("SubString{startIndex=").append(startIndex). append(", length=") .append(len).append(", islands=") .append(islands).append(", numberOfIndexes=") .append(size).append(", arr="); for(int i=startIndex; i<startIndex+len; i++){ sb.append(str[i]).append(','); } sb.setCharAt(sb.length()-1,'}'); return sb.toString(); } } } } c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython