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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Letter Islands
  5. Discussions

Letter Islands

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 17 Discussions, By:

votes

Please Login in order to post a comment

  • shehanjayalath
    2 years ago+ 0 comments

    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);
    }
    
    1|
    Permalink
  • bhautik4avenger4
    4 weeks ago+ 0 comments

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

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

    0|
    Permalink
  • rsvarun93
    5 years ago+ 0 comments

    I've already submitted the code and not all the test cases were correct. When I'm trying to submit again, the code which is working in my terminal is reportedly not clearing even sample test case.

    I even downloaded some test cases from the previous submissions and checked on them in my terminal. They are also working fine.( test case #6) What should I do now

    0|
    Permalink
  • rajeesh
    5 years ago+ 1 comment

    Hello,

    My code has passed 26 test cases and shows timeout for 7 test cases (#12 and 26-31). On "submissions" page I can see timeout as 3s but on my PC the code is producing correct output for #12 in about 2s and for #29 about 1s. Can anyone please tell me what is the real timeout?

    Best Regards

    0|
    Permalink
  • croocroo
    6 years ago+ 2 comments

    For Test Case #5. Here's the input and expected output: Input: aaaabababbaabaaabababbababaabaababaababaabaababaaa 3 Output: 5

    However, should the output be 7? Here are the 7 substrings that I get that create 3 islands: aaa baaba aabaa ababaa babaa abaaba baabaa

    Let me know your thoughts.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature