Ashton and String – HackerRank Solution

In this post, we will solve Ashton and String HackerRank Solution. This problem (Ashton and String) is a part of HackerRank Problem Solving series.

Contents

Ashton and String – HackerRank Solution

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

Python

import os
import sys

def ashtonString(s, k):
    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()

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

Note: This problem (Ashton and String) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

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