HackerRank Ashton and String problem solution

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.

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

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