In this post, we will solve Ashton and String HackerRank Solution. This problem (Ashton and String) is a part of HackerRank Problem Solving series.
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.