HackerRank Ashton and String problem solution

YASH PAL,

In this HackerRank Ashton and String problem solution, we have given the string s and we first need to find its distinct substrings and then sort them and concatenate them and make another string and then print the kth value enter by the user. and this will be the answer.

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?

Function Description

Complete the ashtonString function in the editor below. It should return the kth character from the concatenated string, 1-based 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.

HackerRank Ashton and String problem solution

HackerRank Ashton and String problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the ashtonString function below.
#
def ashtonString(s, k):
    #
    # Write your code here.
    #
    kv = k - 1
    N = len(s)
    sr = [[0 for _ in range(N)] for __ in range(17)]
    sr[0] = [ord(c)-97 for c in s]
    
    L = [0]*N
    cnt = 1
    kf = lambda x: x[0]*(N+1) + x[1]
    for i in range(1, 17):
        for j in range(N):
            L[j] = (sr[i-1][j], sr[i-1][j+cnt] if j+cnt < N else -1, j)
        L.sort(key=kf)
        
        sr[i][L[0][2]] = 0
        cr = 0
        for j in range(1, N):
            if L[j-1][0] != L[j][0] or L[j-1][1] != L[j][1]:
                cr += 1
            sr[i][L[j][2]] = cr
        cnt *= 2
        if cnt >= N:
            break
        
    sa = [l[2] for l in L]
    rank = [0]*N
    lcp = [0]*N
    
    for i in range(N):
        rank[sa[i]] = i
        
    k = 0
    for i in range(N):
        if rank[i] == N-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while j + k < N and i + k < N and s[i+k] == s[j+k]:
            k += 1
        lcp[rank[i]] = k
        if k > 0:
            k -= 1
        
    numprev = 0
    tri = lambda x: ((x+1)*x)>>1
    print(sa)
    print(lcp)
    for i in range(N):
        mylen = N - sa[i]
        tt = tri(mylen) - tri(numprev)
        if kv < tt:
            for j in range(1 + numprev, 1 + mylen):
                if kv < j:
                    return s[sa[i]+kv]
                kv -= j
        kv -= tt
        numprev = lcp[i]
        
    return ''
                
                
        

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        s = input()

        k = int(input())

        res = ashtonString(s, k)

        fptr.write(str(res) + 'n')

    fptr.close()

Ashton and String problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    
    static char ashtonString(String a, int k) {

        TreeSet<String> subStringSet = new TreeSet<>();
        //TreeSet<String> nextSubStringSet = new TreeSet<>();
        TreeSet<String> resultSet = new TreeSet<>();

        int index = -1;
        long len   = a.length();
        int tempIndex = 1;
        String str = a;
        int charIndex = -1;
        int finalLen = 0;
        for(int i=97; i<123; i++){

            //System.out.println(i+"-----"+i);
            str = a;
            int fromIndex = 0;
            while ((charIndex=str.indexOf(i,fromIndex)) != -1){
                str = str.substring(charIndex);
                subStringSet.add(str);
                fromIndex=1;
                //str = str.replaceFirst("["+((char)i)+"]", "");
            }
            while((str=subStringSet.pollFirst())!=null) {
                if (str.length() > 1) {
                    //char ch = str.charAt(0);
                    if (str.charAt(1) == i) {
                        //subStringSet.add(str.replaceFirst("["+ch+"]", ""));
                    }else if (str.charAt(0) != i) {
                        //nextSubStringSet.add(str.substring(1));
                        subStringSet.clear();
                        resultSet.clear();
                        break;
                    }
                }

                len = str.length();
                tempIndex = 0;
                long totLen = (len*(len+1))/2;
                if(totLen >= k){
                //if((len*(len+1))/2 >= k){
                    int lenFnd = 0;
                    for(String strFnd : resultSet){
                        if(str.startsWith(strFnd)){
                            lenFnd += strFnd.length();
                        }
                    }
                    k+=lenFnd;
                    for (int n=1;n<=len;n++){
                        if((n*(n+1))/2 > k){
                            int diff = k-((n-1)*n)/2;
                            return str.charAt(diff-1);
                        } else if((n*(n+1))/2 == k){
                            return str.charAt(n-1);
                        }
                    }
                } else {
                    while (tempIndex++ < (len > 100 ? 100 : len)) {
                        String res = str.substring(0, tempIndex);
                        if (resultSet.add(res)) {
                            k -= res.length();
                        }
                    }

                    for(int n=tempIndex;n<len+1;n++){
                        k-=n;
                    }
                    resultSet.add(str);
                }
            }
        }

        return '$';
    }
    
    static char ashtonString7(String a, int k) {

        TreeSet<String> subStringSet = new TreeSet<>();
        //TreeSet<String> nextSubStringSet = new TreeSet<>();
        TreeSet<String> resultSet = new TreeSet<>();

        int index = -1;
        int len   = a.length();
        int tempIndex = 1;
        String str = a;
        int charIndex = -1;
        int finalLen = 0;
        for(int i=97; i<123; i++){

            //System.out.println(i+"-----"+i);
            str = a;
            while ((charIndex=str.indexOf(i)) != -1){
                str = str.substring(charIndex+1);
                subStringSet.add((char)i+str);
            }

            while((str = subStringSet.pollFirst())!=null) {

                if (str.length() > 1) {
                     if (str.charAt(1) == i) {
                        subStringSet.add(str.substring(1));
                    }else if (str.charAt(0) != i) {
                        //nextSubStringSet.add(str.substring(1));
                        subStringSet.clear();
                        resultSet.clear();
                        break;
                    }
                }

                len = str.length();
                tempIndex = 0;

                while (tempIndex++ < len) {
                    String res = str.substring(0, tempIndex);
                    if (resultSet.add(res)) {
                        if (res.length() >= k) {
                            char ch = res.charAt(k - 1);
                            resultSet.clear();
                            subStringSet.clear();
                            //nextSubStringSet.clear();
                            resultSet = null;
                            subStringSet = null;
                            //nextSubStringSet = null;
                            return ch;
                        } else {
                            k -= res.length();
                        }
                    }
                }

            }
        }

        return '$';
    }
    
    static char ashtonString1(String a, int k) {

        TreeSet<String> subStringSet = new TreeSet<>();
        TreeSet<String> resultSet = new TreeSet<>();

        int index = 0;
        int len   = a.length();
        int tempIndex = 1;

        while (index < len){
            subStringSet.add(a.substring(index++));
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (true){

            String str = subStringSet.pollFirst();

            if(str.length() > 1){
                subStringSet.add(str.substring(1));
            }

            len   = str.length();
            tempIndex = 0;

            while (tempIndex++ < len){
                String res = str.substring(0, tempIndex);
                if(resultSet.add(res)){
                    stringBuilder.append(res);
                }
            }

            int strLen = stringBuilder.length();
            if(strLen > k){
                char ch = stringBuilder.charAt(k-1);
                resultSet.clear();
                subStringSet.clear();
                resultSet = null;
                subStringSet = null;
                stringBuilder = null;
                return ch;
            }
        }
    }
    
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String s = scanner.nextLine();

            int k = Integer.parseInt(scanner.nextLine().trim());

            char res = ashtonString(s, k);

            bufferedWriter.write(String.valueOf(res));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 100005;
typedef long long LL;
int n, k, sa[MAX_N], rk[MAX_N], lcp[MAX_N], tmp[MAX_N];

bool compare_sa(int i, int j) {
    if (rk[i] != rk[j]) return rk[i] < rk[j];
    int ri = i + k <= n ? rk[i + k] : -1;
    int rj = j + k <= n ? rk[j + k] : -1;
    return ri < rj;
}

void construct_sa(const string &S, int *sa) {
    n = S.length();
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rk[i] = (i < n ? S[i] : -1);
    }
    
    for (k = 1; k <= n; k *= 2) {
        sort(sa, sa + n + 1, compare_sa);
        
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) rk[i] = tmp[i];
    }
}

void construct_lcp(const string &S, int *sa, int *lcp) {
    n = S.length();
    for (int i = 0; i <= n; i++) rk[sa[i]] = i;
    
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[rk[i] - 1];
        
        if (h > 0) h--;
        for (; i + h < n && j + h < n; h++) if (S[i + h] != S[j + h]) break;
        
        lcp[rk[i] - 1] = h;
    }
} 

string S;

void solve(LL k) {
    n = S.length();
    construct_sa(S, sa);
    construct_lcp(S, sa, lcp);   
    
    for (int i = 0; i < n; i++) {
        int L = lcp[i];
        int left = n - sa[i + 1];
        LL sum = (L + 1 + left) * (LL)(left - L) / 2;
        if (k > sum) {k -= sum;}
        else {
            for (int j = L + 1; j <= left; j++) {
                if (k <= j) {
                   int index = sa[i + 1] + k;
                   cout << S[index - 1] << endl;
                   return ;
                } else {
                    k -= j;
                }
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        LL k;
        cin >> S >> k;
        solve(k);
    }
    return 0;
}

Problem 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]; 
int rank[N], pos[N], lcp[N];
int cnt[N], next[N]; 
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("%cn",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){

  int h,i,j,k;
  for (i=0; i<n; ++i){
    pos[i] = i;
  }
  sort_a(pos, n);

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


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

Algorithms coding problems solutions

Leave a Reply

Your email address will not be published. Required fields are marked *