HackerRank Letter Islands Problem Solution

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 string
ababaewabaq.
Calculate and print the number of different substrings of string $ that produce exactly k islands.
Input Format
The 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

Explanation

All the suitable substrings are: a, ab, b.

Table of Contents

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

Letter Islands C Solution

Letter Islands C++ Solution

Letter Islands C# Solution

Letter Islands Java Solution

Related Posts

Leave a Reply