HackerRank Ashton and String Solution

Hello Programmers, In this post, you will learn how to solve HackerRank Ashton and String Solution. This problem is a part of the HackerRank Algorithms Series.

One more thing to add, don’t straight away look for the solutions, first try to solve the problems by yourself. If you find any difficulty after trying several times, then look for the solutions. We are going to solve the HackerRank Algorithms problems using C, CPP, JAVA, PYTHON, JavaScript & SCALA Programming Languages.

You can practice and submit all HackerRank problem solutions in one place. Find a solution for other domains and Sub-domain. I.e. Hacker Rank solution for HackerRank C ProgrammingHackerRank C++ ProgrammingHackerRank Java Programming, HackerRank Python ProgrammingHackerRank Linux ShellHackerRank SQL Programming, and HackerRank 10 days of Javascript.

Ashton and String  problem solution
Ashton and String problem solution

As you already know that this site does not contain only the Hacker Rank solutions here, you can also find the solution for other problems. I.e. Web Technology, Data StructuresRDBMS ProgramsJava Programs Solutions,  Fiverr Skills Test answersGoogle Course AnswersLinkedin Assessment, and Coursera Quiz Answers.

HackerRank Ashton and String

Task

Ashton appeared for a job interview and is asked the following question. Arrange all the distinct substrings of a given string in lexicographical order and concatenate them. Print the kth character of the concatenated string. It is assured that given value of k will be valid i.e. there will be a kth character. Can you help Ashton out with this?

For example, given the string s = abc, its distinct substrings are [a, ab, abc, abcd, b, bc, bcd, c, cd, d]. Sorted and concatenated, they make the string aababcabcdbbcbcdccdd. If K = 5 then, the answer is b, the 5th character of the 1-indexed concatenated string.

Note We have distinct substrings here, i.e. if string is aa, it’s distinct substrings are a and aa.

Function Description

Complete the ashtonString function in the editor below. It should return the kth character from the concatenated string, 1based indexing.

ashtonString has the following parameters:
– s: a string
– k: an integer

Input Format

The first line will contain an integer t, the number of test cases.

Each of the subsequent t pairs of lines is as follows:
– The first line of each test case contains a string, s.
– The second line contains an integer, k.

Constraints

  • 1 <= t <= 5
  • 1 <= |s| <= 105
  • Each character of string s ∈ ascii[a – z]
  • k will be an appropriate integer.

Output Format

Print the kth character (1based index) of the concatenation of the ordered distinct substrings of s.

Sample Input

1
dbac
3

Sample Output

c

Explanation

The substrings when arranged in lexicographic order are as follows

a, ac, b, ba, bac, c, d, db, dba, dbac

On concatenating them, we get

aacbbabaccddbdbadbac

The third character in this string is c.

HackerRank Ashton and String Solution

Ashton and String Solution in C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 100001
void merge(int*a,int*left,int*right,int left_size, int right_size);
void sort_a(int*a,int size);
void suffixSort(int n);
void LCP(int n);
char str[N]; //input
int rank[N], pos[N], lcp[N]; //output
int cnt[N], next[N]; //internal
int bh[N], b2h[N];

int main(){
  char cc;
  int T,n,i;
  long long K,c,t,x,tt;
  double xx;
  scanf("%d",&T);
  while(T--){
    scanf("%s%lld",str,&K);
    n=strlen(str);
    suffixSort(n);
    LCP(n);
    c=0;
    for(i=0;i<n;i++){
      tt=c;
      c+=(lcp[i]+1+n-pos[i])*(long long)(n-pos[i]-lcp[i])/2;
      if(K<=c){
        xx=(-1+sqrt(4*(2*(K-tt)+lcp[i]+lcp[i]*(long long)lcp[i])))/2;
        x=(long long)xx;
        t=K-tt-(lcp[i]+1+x)*(x-lcp[i])/2;
        if(!t)
          cc=str[pos[i]+x-1];
        else
          cc=str[pos[i]+t-1];
        break;
      }
    }
    printf("%c\n",cc);
  }
  return 0;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (str[left[i]] <= str[right[j]]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
 
void suffixSort(int n){
  //sort suffixes according to their first characters
  int h,i,j,k;
  for (i=0; i<n; ++i){
    pos[i] = i;
  }
  sort_a(pos, n);
  //{pos contains the list of suffixes sorted by their first character}
 
  for (i=0; i<n; ++i){
    bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
    b2h[i] = 0;
  }
 
  for (h = 1; h < n; h <<= 1){
    //{bh[i] == false if the first h characters of pos[i-1] == the first h characters of pos[i]}
    int buckets = 0;
    for (i=0; i < n; i = j){
      j = i + 1;
      while (j < n && !bh[j]) j++;
      next[i] = j;
      buckets++;
    }
    if (buckets == n) break; // We are done! Lucky bastards!
    //{suffixes are separted in buckets containing strings starting with the same h characters}
 
    for (i = 0; i < n; i = next[i]){
      cnt[i] = 0;
      for (j = i; j < next[i]; ++j){
        rank[pos[j]] = i;
      }
    }
 
    cnt[rank[n - h]]++;
    b2h[rank[n - h]] = 1;
    for (i = 0; i < n; i = next[i]){
      for (j = i; j < next[i]; ++j){
        int s = pos[j] - h;
        if (s >= 0){
          int head = rank[s];
          rank[s] = head + cnt[head]++;
          b2h[rank[s]] = 1;
        }
      }
      for (j = i; j < next[i]; ++j){
        int s = pos[j] - h;
        if (s >= 0 && b2h[rank[s]]){
          for (k = rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = 0;
        }
      }
    }
    for (i=0; i<n; ++i){
      pos[rank[i]] = i;
      bh[i] |= b2h[i];
    }
  }
  for (i=0; i<n; ++i){
    rank[pos[i]] = i;
  }
}
// End of suffix array algorithm

void LCP(int n){
  int l=0,i,j,k;
  for(i=0;i<n;i++){
    k=rank[i];
    if(!k)
      continue;
    j=pos[k-1];
    while(str[i+l]==str[j+l])
      l++;
    lcp[k]=l;
    if(l>0)
      l--;
  }
  lcp[0]=0;
  return;
}

Ashton and String Solution in Cpp

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MAXLEN = (int)1e5 + 5;

char s[MAXLEN];
int SA[MAXLEN], cnt[MAXLEN], ary1[MAXLEN], ary2[MAXLEN];
int *Rank, *Height;


inline bool cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void make_suffix_array(int MSIZE, int len) {
    int p, *x, *y, *tmp, i, j, k;
    x = ary1; y = ary2;
    memset(cnt, 0, sizeof(int) * MSIZE);
    for (i = 0; i < len; i++) cnt[x[i] = s[i]]++;
    for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
    for (i = len - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
    for (j = p = 1; p < len; j <<= 1, MSIZE = p) {
        for (p = 0, i = len - j; i < len; i++) y[p++] = i;
        for (i = 0; i < len; i++) {
            if (SA[i] >= j) y[p++] = SA[i] - j;
        }
        memset(cnt, 0, sizeof(int) * MSIZE);
        for (i = 0; i < len; i++) cnt[x[y[i]]]++;
        for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
        for (i = len - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
        tmp = x; x = y; y = tmp;
        x[SA[0]] = 0;
        for (i = p = 1; i < len; i++) {
            x[SA[i]] = cmp(y, SA[i - 1], SA[i], j) ? p - 1 : p++;
        }
    }
    Rank = x;
    Height = y;
    for (i = k = 0; i < len - 1; i++) {
        if (k > 0) k--;
        j = SA[Rank[i] - 1];
        while (s[i + k] == s[j + k]) k++;
        Height[Rank[i]] = k;
    }
}
LL get(LL x,LL y){
    return (x+y)*(y-x+1)/2;
}
int main(){
    CASET{
        RS(s);
        int n=LEN(s);
        LL K;
        cin>>K;
        make_suffix_array(128,n+1);
        int now=0;
        REPP(i,1,n+1){
            now=Height[i];
            if(K<=get(now+1,n-SA[i])){
                LL ll=now+1,rr=n-SA[i];
                while(ll<rr){
                    LL mm=(ll+rr)>>1;
                    if(get(now+1,mm)<K)ll=mm+1;
                    else rr=mm;
                }
                K-=get(now+1,ll-1);
                printf("%c\n",s[SA[i]+K-1]);
                break;
            }
            else K-=get(now+1,n-SA[i]);
        }
    }
    return 0;
}

Ashton and String Solution in Java

import java.io.*;
import java.util.*;
public class Solution {
	private static final int mod = (int)1e9+7;

	final Random random = new Random(0);

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		 for(int t=sc.nextInt();t>0;t--) {
			char[] cs = sc.next().toCharArray();
			int K = sc.nextInt();
			SuffixArray sa = new SuffixArray(cs);
			System.out.println(sa.kthDistinctSubstring(K));

		}
		 sc.close();
	}


	static
	public class SuffixArray {
		private static final char[] mask = new char[] { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
		
		private static boolean tget(final byte[] t, final int i) { return (t[i>>>3]&mask[i&7]) != 0; }
		private static void tset(final byte[] t, final int i, final boolean b) { 
			if(b) {
				t[i>>>3] |= mask[i&7];
			} else {
				t[i>>>3] &= ~mask[i&7];
			}
		}
		
		private static boolean isLMS(final byte[] t, final int i) { return i > 0 && tget(t, i) && !tget(t, i-1); }
		
		private static void getBuckets(final Slice s, int[] bkt, int n, int K, boolean end) {
			Arrays.fill(bkt, 0);
			for(int i = 0; i < n; i++) {
				bkt[s.get(i)]++;
			}
			for(int i = 0, sum = 0; i <= K; i++) {
				sum += bkt[i];
				bkt[i] = end ? sum : sum - bkt[i];
			}
		}
		
		private static void induceSAl(final byte[] t, final Slice SA, final Slice s, int[] bkt, int n, int K, boolean end) {
			getBuckets(s, bkt, n, K, end);
			for(int i = 0; i < n; i++) {
				final int j = SA.get(i) - 1;
				if(j >= 0 && !tget(t, j)) {
					SA.set(bkt[s.get(j)]++, j);
				}
			}
		}
		
		private static void induceSAs(final byte[] t, final Slice SA, final Slice s, int[] bkt, int n, int K, boolean end) {
			getBuckets(s, bkt, n, K, end);
			for(int i = n - 1; i >= 0; i--) {
				final int j = SA.get(i) - 1;
				if(j >= 0 && tget(t, j)) {
					SA.set(--bkt[s.get(j)], j);
				}
			}
		}
		
		private static void build(final Slice s, final Slice SA, final int n, final int K) {
			final byte[] t = new byte[n/8+1];
			
			tset(t, n-2, false);
			tset(t, n-1, true);
			
			for(int i = n - 3; i >= 0; i--) {
				tset(t, i, s.get(i) < s.get(i+1) || s.get(i) == s.get(i+1) && tget(t, i+1));
			}
			
			// stage 1
			final int[] bkt = new int[K + 1];
			getBuckets(s, bkt, n, K, true);
			for(int i = 0; i < n; i++) {
				SA.set(i, -1);
			}
			
			for(int i = 1; i < n; i++) {
				if(isLMS(t, i)) {
					SA.set(--bkt[s.get(i)], i);
				}
			}

			induceSAl(t, SA, s, bkt, n, K, false);
			induceSAs(t, SA, s, bkt, n, K, true);
			
			int n1 = 0;
			for(int i = 0; i < n; i++) {
				if(isLMS(t, SA.get(i))) {
					SA.set(n1++, SA.get(i));
				}
			}
			
			for(int i = n1; i < n; i++) {
				SA.set(i, -1);
			}
			
			int name = 0, prev = -1;
			for(int i = 0; i < n1; i++) {
				int pos = SA.get(i);
				boolean diff = false;
				for(int d = 0; d < n; d++) {
					if(prev == -1
					|| s.get(pos+d) != s.get(prev+d)
					|| (tget(t, pos+d) ^ tget(t, prev+d))) {
						diff = true;
						break;
					} else if(d > 0 && (isLMS(t, pos+d) || isLMS(t, prev+d))) {
						break;
					}
				}
				if(diff) { name++; prev = pos; }
				pos >>>= 1;
				SA.set(n1+pos, name - 1);
			}
			
			for(int i = n - 1, j = n - 1; i >= n1; i--) {
				if(SA.get(i) >= 0) {
					SA.set(j--, SA.get(i));
				}
			}
			
			// stage 2
			final Slice SA1 = new Slice(SA, 0);
			final Slice s1 = new Slice(SA, n - n1);
			if(name < n1) {
				build(s1, SA1, n1, name - 1);
			} else {
				for(int i = 0; i < n1; i++) {
					SA1.set(s1.get(i), i);
				}
			}
			
			// stage 3
//			bkt = new int[K + 1];
			getBuckets(s, bkt, n, K, true);
			for(int i = 1, j = 0; i < n; i++) {
				if(isLMS(t, i)) {
					s1.set(j++, i);
				}
			}
			
			for(int i = 0; i < n1; i++) {
				SA1.set(i, s1.get(SA1.get(i)));
			}
			
			for(int i = n1; i < n; i++) {
				SA.set(i, -1);
			}
			for(int i = n1 - 1, j; i >= 0; i--) {
				j = SA.get(i);
				SA.set(i, -1);
				SA.set(--bkt[s.get(j)], j);
			}
			induceSAl(t, SA, s, bkt, n, K, false);
			induceSAs(t, SA, s, bkt, n, K, true);
		}
		
		private static int[] constructSA(final int[] s_, final int n, final int K) {
			final Slice s = new Slice(s_, 0);
			final Slice SA = new Slice(new int[n], 0);
			build(s, SA, n, K);

			return SA.ary;
		}
		
		
		
		private final int n;
		private final char[] cs;
		public final int[] sa, lcp, rank;
		public SuffixArray(final char[] cs) {
			this.cs = cs;
			int[] input = new int[cs.length + 1];
			for(int i = 0; i < cs.length; i++) {
				input[i] = cs[i] - 'a' + 1;
			}
			sa = constructSA(input, input.length, 27);
			n = cs.length;
			rank = new int[n + 1];
			lcp = new int[n];
			constructLcp();
		}
		
		private void constructLcp() {
			for(int i = 0; i <= n; i++) {
				rank[sa[i]] = i;
			}
			
			int h = 0;
			lcp[0] = 0;
			for(int i = 0; i < n; i++) {
				final int j = sa[rank[i] - 1];
				if(h > 0) h--;
				for(; j + h < n && i + h < n; h++) {
					if(cs[j + h] != cs[i + h]) {
						break;
					}
				}
				lcp[rank[i] - 1] = h;
			}
		}
		
		private static class Slice {
			private final int shift;
			private final int[] ary;
			
			public int get(final int idx) { return ary[shift + idx]; }
			public void set(final int idx, final int val) { ary[shift + idx] = val; }
			
			public Slice(final int[] ary, final int shift) {
				this.ary = ary;
				this.shift = shift;
			}
			
			public Slice(final Slice s, final int shift) {
				this.ary = s.ary;
				this.shift = s.shift + shift;
			}
		}
		
		public long numberOfDistinctSubstrings() {
			long ret = 0;
			for(int i = 1; i <= n; i++) {
				ret += n - sa[i] - lcp[i - 1];
			}
			return ret;
		}
		
		public char kthDistinctSubstring(long k) {
			for(int i = 1; ; i++) {
				for(int j = sa[i] + lcp[i-1]; j < n; j++) {
					for(int l = sa[i]; l <= j; l++) {
						if(--k == 0) {
							return cs[l];
						}
					}
				}
			}
		}
		

		public static long numberOfDistinctSubstringsNaive(String s) {
			Set<String> set = new TreeSet<String>();
			for(int i = 0; i < s.length(); i++) {
				for(int j = i + 1; j <= s.length(); j++) {
					set.add(s.substring(i, j));
				}
			}
			return set.size();
		}
		
		public static String kthDistinctSubstringNaive(String s, long k) {
			TreeSet<String> set = new TreeSet<String>();
			for(int i = 0; i < s.length(); i++) {
				for(int j = i + 1; j <= s.length(); j++) {
					set.add(s.substring(i, j));
				}
			}
			while(k-- > 0 && !set.isEmpty()) { set.pollFirst(); }
			return set.isEmpty() ? " " : set.first();
		}
	}

}

Ashton and String Solution in Python

def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ""
	last_suffix = ""
	for suffix in suffixes:

		# first, if this is a repeat, skip it
		if suffix == last_suffix:
			continue
		
		idx = 0
		
		# second, if this is the first value, process the entire thing
		if last_suffix != "":
			idx = 1 # first letter will always be the same
			while idx < len(suffix) and idx < len(last_suffix) and last_suffix[idx] == suffix[idx]:
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		
		last_suffix = suffix

	return (None, k)
	
ALPHABET = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
			'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def make_suffix_dict(word):
	suffix_indexes = dict()
	
	for i, ch in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
		
	return suffix_indexes
	
def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes
	
def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			
			if ch:
				return ch


test_cases = int(input())

for i in range(0, test_cases):
	line = raw_input()
	k = int(raw_input()) - 1
	print find_kth_char(line, k)

Ashton and String Solution using JavaScript

function processData(input) {
    input = input.split("\n");
    var read = 0;
    var tests = input[read++];

    for(var test=0; test<tests; test++) {
      word = input[read++];
      k = input[read++];
      
      run_test_case(word,k);      
    }
}

function run_test_case(s, k) {
    var A = s;
    var index = 0;

    var object = calculateSuffixArrayLCPAndIntervals(A);
    var response = search_character(object.suffix_array, object.intervals, k, A, object.lcp_array);    
    console.log(response);
} 

function findIndex(a, start, end, target) {
  var mid;
  while (start <= end) {
    mid = Math.floor((start + end) / 2);
    if (target == a[mid]) {
      return mid;
    } else if (target < a[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return start;
}
    
function search_character(suffixes, intervals, k, A, lcp_array) {
  var response;
  var index = findIndex(intervals, 0, intervals.length - 1, k);

  if (index > intervals.length - 1) {
    response = "INVALID";
  } else {

    var begin = intervals[index-1];
    var char_pos = k - begin;

    var current = A.substring(suffixes[index - 1], A.length);

    var lcp = lcp_array[index-1];
    var substrings = current.length - lcp;
    var string_interval = [0];
    for(var i=0; i<substrings; i++) {
      string_interval.push(current.length-substrings+i+1 + string_interval[string_interval.length-1]);
    }

    var char_index = findIndex(string_interval, 0, string_interval.length-1, char_pos);

    var current_substring = current.substring(0, current.length-substrings+char_index);
    //console.log(current_substring);
    //console.log(char_pos);
    var current_pos = char_pos - string_interval[char_index-1]; 
    response = current_substring[current_pos-1];
  }
  return response;
}

///**********


function calculateSuffixArrayLCPAndIntervals(A) {
  var MAXLG = 17;
  var N = A.length;
  var P = [];
  P.push([]);

  for(var i=0; i<N; i++) {
    P[0][i] = A[i].charCodeAt(0) - 'a'.charCodeAt(0);   
  }
  var L = [];

  var step = 1;
  var count = 1;
  var maximum_prefix_size = A.length;
  for(step=1,count=1; count >> 1 < maximum_prefix_size; step++, count <<= 1) {
    P.push([]);
    for(var i=0; i<N; i++) {
      var nr0 = P[step-1][i];
      var nr1 = i + count < N ? P[step-1][i+count]:-1;
      var p = i;
      L[i] = { nr0: nr0, nr1: nr1, p:p };
    }

    L.sort(function(a,b) { return a.nr0==b.nr0 ? ( a.nr1<b.nr1 ? -1 : 1) : (a.nr0 < b.nr0) ? -1 : 1 });

    for(var i=0; i<N; i++) {
      P[step][L[i].p] = i > 0 && L[i].nr0 == L[i-1].nr0 && L[i].nr1 == L[i-1].nr1 ? P[step][L[i-1].p] : i;
    }
  }
  
  suffix_array = []
  for(var i=0; i<N; i++) {
    suffix_array.push( L[i].p );
  }
        
  //L has the ordered indexes, create lcp for consecutive pairs with it
  var lcp_array = [0]
  for(var i=1; i<N; i++) {
    lcp_array.push(lcp(L[i-1].p,L[i].p,P,step,N));
  }
  
  var intervals = characters_intervals(A, suffix_array,lcp_array);

  return { suffix_array: suffix_array, string: A, lcp_array: lcp_array, intervals: intervals }
}

function lcp(x,y,P,step,N) {
  var k = 0;
  var ret = 0;
  if(x==y) return N-x;
  for(k=step-1; k>=0 && x<N && y<N; k--) 
    if(P[k][x] == P[k][y]) 
      x+=1 << k, y+=1 << k, ret += 1 << k;
  return ret;
}

function characters_intervals(A, suffix_array, lcp_array) {
 
  var intervals = [ 0 ];

  for(var i=0; i<lcp_array.length; i++) {
    var size_of_suffix = A.length - suffix_array[i];
    var substrings = size_of_suffix - lcp_array[i];
    var ap = (substrings-1 > 0) ? ((substrings-1)*(1+(substrings-1)))/2 : 0;
    var characters = ( size_of_suffix * substrings ) - ap;
    var interval = intervals[intervals.length-1] + characters;
    intervals.push(interval);
  }

  return intervals;
}



process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Ashton and String Solution in Scala

object Solution extends App {
  def makeLcpArray(pos: Array[Int], sa: Array[Int], lcp: Array[Int]): Unit = {
    val n = sa.length
    val rank = Array.ofDim[Int](n)
    
    pos(n) = -1
    
    for (i <- 0 until n) rank(sa(i)) = i
    
    var h = 0
    for (i <- 0 until n if rank(i) > 0) {
      val j = sa(rank(i) - 1)
      while (pos(i + h) == pos(j + h)) h += 1
      lcp(rank(i)) = h
      
      if (h > 0) h -= 1
    }
  }
  
  def createSuffixArray(str: String, sa: Array[Int], LCP: Array[Int]): Unit = {
    val n = str.length( );
        
    val s = Array.ofDim[Int](n + 3)
    val SA = Array.ofDim[Int](n + 3)
    
    for (i <- 0 until n) {
      s(i) = str(i)
    }
    
    makeSuffixArray(s, SA, n, 256 )
    
    for (i <- 0 until n) {
      sa(i) = SA(i)
    }
    //println(str)
    //println(sa.mkString(", "))
    makeLcpArray(s, sa, LCP)
    //println(LCP.mkString(", "))
  }
  
  def makeSuffixArray(s: Array[Int], sa: Array[Int], n: Int, k: Int): Unit = {
    val n0 = (n + 2) / 3
    val n1 = (n + 1) / 3
    val n2 = n / 3
    val t = n0 - n1  // 1 iff n%3 == 1
    val n12 = n1 + n2 + t
    
    val s12  = Array.ofDim[Int](n12 + 3)
    val SA12 = Array.ofDim[Int](n12 + 3)
    val s0   = Array.ofDim[Int](n0)
    val SA0  = Array.ofDim[Int](n0)
    
    var j = 0
    for (i <- 0 until n + t if i % 3 != 0){
      s12(j) = i
      j += 1
    }
    
    val k12 = assignNames(s, s12, SA12, n0, n12, k)
  
    computeS12(s12, SA12, n12, k12)
    computeS0(s, s0, SA0, SA12, n0, n12, k)
    merge(s, s12, sa, SA0, SA12, n, n0, n12, t)
  }
  
  def assignNames(s: Array[Int], s12: Array[Int], sa12: Array[Int], n0: Int, n12: Int, k: Int): Int = {
    radixPass(s12 , sa12, s, 2, n12, k)
    radixPass(sa12, s12 , s, 1, n12, k)  
    radixPass(s12 , sa12, s, 0, n12, k);
    
    var name = 0
    var c0 = -1
    var c1 = -1
    var c2 = -1
    
    for (i <- 0 until n12) {
      if (s(sa12(i)) != c0 || s(sa12(i) + 1) != c1 || s(sa12(i) + 2) != c2) {
        name += 1
        c0 = s(sa12(i))
        c1 = s(sa12(i) + 1)
        c2 = s(sa12(i) + 2)
      }
      
      if(sa12(i) % 3 == 1) s12(sa12(i) / 3) = name;
      else s12(sa12(i) / 3 + n0) = name
    }
    
    name
  }
  
  def radixPass(in: Array[Int], out: Array[Int], s: Array[Int], offset: Int, n: Int, k: Int): Unit = {
    val count = Array.ofDim[Int](k + 2)
    
    for (i <- 0 until n) {
      count(s(in(i) + offset) + 1) += 1
    }
    
    for (i <- 1 to k + 1) {
      count(i) += count(i - 1)
    }
    
    for (i <- 0 until n) {
      out(count(s(in(i) + offset))) = in(i)
      count(s(in(i) + offset)) += 1
    }
  }
  
  def radixPass(in: Array[Int], out: Array[Int], s: Array[Int], n: Int, k: Int): Unit = {
    radixPass(in, out, s, 0, n, k)
  }
  
  def computeS12(s12: Array[Int], sa12: Array[Int], n12: Int, k12: Int): Unit = {
    if (k12 == n12) {
      for (i <- 0 until n12) {
        sa12(s12(i) - 1) = i
      }
    } else {
      makeSuffixArray(s12, sa12, n12, k12)
      for (i <- 0 until n12) {
        s12(sa12(i)) = i + 1
      }
    }
  }
  
  def computeS0(s: Array[Int], s0: Array[Int], sa0: Array[Int], sa12: Array[Int], n0: Int, n12: Int, k: Int): Unit = {
    var j = 0
    for (i <- 0 until n12 if sa12(i) < n0) {
      s0(j) = 3 * sa12(i)
      j += 1
    }
    radixPass(s0, sa0, s, n0, k)
  }
  
  def merge(s: Array[Int], s12: Array[Int], sa: Array[Int], sa0: Array[Int], sa12: Array[Int], n: Int, n0: Int, n12: Int, u: Int): Unit = {
    var p = 0
    var k = 0
    var t = u
    
    while(t != n12 && p != n0) {
      val i = getIndexIntoS(sa12, t, n0)
      val j = sa0(p)
      
      if(suffix12IsSmaller(s, s12, sa12, n0, i, j, t )) {
        sa(k) = i
        k += 1
        t += 1
      } else {
        sa(k) = j
        k += 1
        p += 1
      }
    }
    
    while(p < n0) {
      sa(k) = sa0(p)
      k += 1
      p += 1
    } 
    
    while (t < n12) {
      sa(k) = getIndexIntoS(sa12, t, n0)
      k += 1
      t += 1
    }
  }
  
  def getIndexIntoS(sa12: Array[Int], t: Int, n0: Int): Int = {
    if(sa12(t) < n0)
      sa12(t) * 3 + 1;
    else
      (sa12(t) - n0) * 3 + 2
  }
  
  def leq(a1: Int, a2: Int, b1: Int, b2: Int): Boolean = a1 < b1 || a1 == b1 && a2 <= b2
  
  def leq(a1: Int, a2: Int, a3: Int, b1: Int, b2: Int, b3: Int): Boolean = a1 < b1 || a1 == b1 && leq( a2, a3,b2, b3 )
  
  def suffix12IsSmaller(s: Array[Int], s12: Array[Int], sa12: Array[Int], n0: Int, i: Int, j: Int, t: Int): Boolean = {
    if( sa12(t) < n0 )  // s1 vs s0; can break tie after 1 character
            return leq( s(i), s12(sa12(t) + n0),
                        s(j), s12(j / 3) );
        else                  // s2 vs s0; can break tie after 2 characters
            return leq( s(i), s(i + 1), s12(sa12(t) - n0 + 1),
                        s(j), s(j + 1), s12(j / 3 + n0) )
  }
  
  def solve(s: String, k: Int): Char = {
    val len = s.length
    
    val sufarr = Array.ofDim[Int](len)
    val LCP = Array.ofDim[Int](len)

    createSuffixArray(s, sufarr, LCP);
    
    var reached = 0
    var con = ""
    for (i <- 0 until sufarr.length if reached < k) {
      var j = LCP(i) + 1
      while (reached < k && j <= len - sufarr(i)) {
        //println(j)
//        if (j < len - sufarr(i)) {
//        	con += s.substring(sufarr(i), sufarr(i) + j)
//        }
        reached += j
        j += 1
      }
      if (reached >= k) {
        //println(con)
        //println(reached)
        val index = k - (reached - j + 2) + sufarr(i)
        //println(index)
        return(s(index))
      }
    }
    
    'd'
  }
  
  val cases = readInt
  
  for (i <- 0 until cases) {
    val s = readLine
    val k = readInt
    println(solve(s, k))
  }
}

Ashton and String Solution in Pascal

Disclaimer: This problem (Ashton and String) is generated by HackerRank but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purposes.

FAQ:

1. How do you solve the first question in HackerRank?

If you want to solve the first question of Hackerrank then you have to decide which programing language you want to practice i.e C programming, Cpp Programing, or Java programming then you have to start with the first program HELLO WORLD.

2. How do I find my HackerRank ID?

You will receive an email from HackerRank to confirm your access to the ID. Once you have confirmed your email, the entry will show up as verified on the settings page. You will also have an option to “Make primary”. Click on that option. Read more

3. Does HackerRank detect cheating?

yes, HackerRank uses a powerful tool to detect plagiarism in the candidates’ submitted code. The Test report of a candidate highlights any plagiarized portions in the submitted code and helps evaluators to verify the integrity of answers provided in the Test.

4. Does HackerRank use camera?

No for coding practice Hackerrank does not use camera but for companies’ interviews code submission time Hackerrank uses the camera.

5. Should I put HackerRank certificate on resume?

These certificates are useless, and you should not put them on your resume. The experience you gained from getting them is not useless. Use it to build a portfolio, and link to it on your resume. 

6. Can I retake HackerRank test?

The company which sent you the HackerRank Test invite owns your Test submissions and results. It’s their discretion to permit a reattempt for a particular Test. If you wish to retake the test, we recommend that you contact the concerned recruiter who invited you to the Test and request a re-invite. 

7. What is HackerRank?

HackerRank is a tech company that focuses on competitive programming challenges for both consumers and businesses. Developers compete by writing programs according to provided specifications. Wikipedi


Finally, we are now, in the end, I just want to conclude some important message for you

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Please share our posts on social media platforms and also suggest to your friends to Join Our Groups. Don’t forget to subscribe. 

Sharing Is Caring

Leave a Comment