We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Letter Islands
  5. Discussions

Letter Islands

Sort by

recency

|

20 Discussions

|

  • Stadnyk90
     + 0 comments

    using System; using System.Collections.Concurrent; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks; class Solution { public static int CountIslands(string s, string p) { int n = s.Length; int m = p.Length; bool[] marked = new bool[n]; // Mark positions covered by substring p using Parallel.For Parallel.For(0, n - m + 1, i => { if (s.Substring(i, m) == p) { for (int j = i; j < i + m; j++) { marked[j] = true; } } }); // Count islands using LINQ int islands = marked .Select((value, index) => new { value, index }) .Aggregate( new { Count = 0, InIsland = false }, (acc, item) => item.value ? acc.InIsland ? acc : new { Count = acc.Count + 1, InIsland = true } : new { Count = acc.Count, InIsland = false }, acc => acc.Count ); return islands; } public static int CountSubstringsWithKIslands(string s, int k) { var substrings = new ConcurrentDictionary(); int n = s.Length; // Generate all substrings and count islands using PLINQ var allSubstrings = from i in Enumerable.Range(0, n) from j in Enumerable.Range(i + 1, n - i) select s.Substring(i, j - i); Parallel.ForEach(allSubstrings.Distinct(), substring => { int islands = CountIslands(s, substring); if (islands == k) { substrings.TryAdd(substring, true); } }); return substrings.Count; } static async Task Main(string[] args) { string s = Console.ReadLine(); int k = int.Parse(Console.ReadLine()); int result = await Task.Run(() => CountSubstringsWithKIslands(s, k)); Console.WriteLine(result); } }

  • yashparihar729
     + 0 comments

    Here is my solution in java, C, C++, Csharp HackerRank Letter Islands Problem Solution

  • mineman1012221
     + 0 comments

    Here is the solution of Letter Islands Click Here

  • bhautik4avenger4
     + 0 comments

    https://zeroplusfour.com/letter-islands/

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

  • shehanjayalath
     + 1 comment

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