HackerRank Ashton and String Problem Solution Yashwant Parihar, May 1, 2023May 1, 2023 In this post, we will solve HackerRank Ashton and String Problem Solution. 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 DescriptionComplete 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. Output Format Print the K character (1-based 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 Problem Solution Ashton and String C Solution #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #define MAX_STRING 100001 static char s[MAX_STRING] ; static unsigned sl ; struct rtree { unsigned b, e ; // prefix beginning / end int leaf ; unsigned n ; struct rtree *more[26] ; } ; static void rt_add(struct rtree *t, unsigned b) { unsigned i, cl = (sl - b > t->e - t->b) ? (t->e - t->b) : (sl - b) ; for (i = 0; i < cl && s[t->b + i] == s[b + i]; i ++) ; if (t->b + i < t->e) { struct rtree *t2 = calloc(sizeof(*t2), 1) ; assert(t2) ; *t2 = *t ; t2->b = t->b + i + 1 ; t->e = t->b + i ; t->leaf = 0 ; memset(&(t->more), 0, sizeof(t->more)) ; t->more[s[t->b + i] - 'a'] = t2 ; } t->n ++ ; assert(sl - b >= t->e - t->b) ; if (sl - b == t->e - t->b) { assert(!t->leaf) ; t->leaf = 1 ; return ; } int ci = s[b + i] - 'a' ; if (t->more[ci]) return rt_add(t->more[ci], b + i + 1) ; struct rtree *t2 = calloc(sizeof(*t2), 1) ; assert(t2) ; t2->b = b + i + 1 ; t2->e = sl ; t2->leaf = 1 ; t2->n = 1 ; t->more[ci] = t2 ; } static struct rtree *rt_init(void) { struct rtree *t = calloc(sizeof(*t), 1) ; assert(t) ; t->b = 0 ; t->e = sl ; t->leaf = 1 ; t->n = 1 ; for (unsigned i = 1; i < sl; i ++) rt_add(t, i) ; return t ; } static void rt_destroy(struct rtree *t) { for (int c = 0; c <= 'z' - 'a'; c ++) if (t->more[c]) rt_destroy(t->more[c]) ; free(t) ; } static void rt_print(struct rtree *t, char key, unsigned pad) { for (int i = 0; i < pad; i ++) putc(' ', stdout) ; putc(key, stdout) ; for (unsigned i = t->b; i < t->e; i ++) putc(s[i], stdout) ; if (t->leaf) printf(" *") ; putc('\n', stdout) ; for (int c = 0; c <= 'z' - 'a'; c ++) if (t->more[c]) rt_print(t->more[c], 'a' + c, pad + 1 + t->e - t->b) ; } static unsigned rt_len(struct rtree *t, int pad) { unsigned n = t->e - t->b ; unsigned l = pad + n * pad + n * (n + 1) / 2 ; for (int c = 0; c <= 'z' - 'a'; c ++) if (t->more[c]) l += rt_len(t->more[c], pad + n + 1) ; return l ; } static int rt_ref(struct rtree *t, int i, int pad) { unsigned n = t->e - t->b ; unsigned l = pad + n * pad + n * (n + 1) / 2 ; if (l > i) { for (int j = 0; j <= n; j ++) { i -= pad ; if (i < 0) return i ; if (i < j) { printf("%c\n", s[t->b + i]) ; return 0 ; } i -= j ; } abort() ; } else i -= l ; for (int c = 0; c <= 'z' - 'a'; c ++) if (t->more[c]) { i = rt_ref(t->more[c], i, pad + n + 1) ; if (!i) return i ; if (i > 0) continue ; if (i == -1) { printf("%c\n", c + 'a') ; return 0 ; } i = t->e - t->b + i + 1 ; if (i >= 0) { printf("%c\n", s[t->b + i]) ; return 0 ; } break ; } return i ; } static int read_int(void) { char b[32] ; assert(fgets(b, sizeof(b), stdin)) ; return atoi(b) ; } int main(int ac, const char *av[]) { int t = read_int() ; while (t --) { assert(fgets(s, sizeof(s), stdin)) ; sl = strlen(s) - 1 ; s[sl] = 0 ; int n = read_int() - 1 ; struct rtree *t = rt_init() ; rt_ref(t, n, 0) ; rt_destroy(t) ; } return 0 ; } Ashton and String C++ Solution #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; } Ashton and String C Sharp Solution using System.CodeDom.Compiler; using System.Collections.Generic; using System.Collections; using System.ComponentModel; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.IO; using System.Linq; using System.Reflection; using System.Runtime.Serialization; using System.Text.RegularExpressions; using System.Text; using System; class Result { /// <summary> /// Compares two suffixes of Source string. Both suffixes are represented by an integer 0-based index of the Source string. /// </summary> internal record StringSuffixComparer(string Source) : IComparer<int> { public int Compare(int x, int y) => Source.AsSpan(x).CompareTo(Source.AsSpan(y), StringComparison.OrdinalIgnoreCase); } public static int[] ConstructOrderedSuffixArray(string source) { var suffixesIndicies = Enumerable.Range(0, source.Length).ToArray(); Array.Sort(suffixesIndicies, new StringSuffixComparer(source)); return suffixesIndicies; } public static int[] CalculateLongestCommonPrefix(string source, int[] orderedSuffixArray) { var lcp = new int[orderedSuffixArray.Length]; lcp[0] = 0; ReadOnlySpan<char> prevSuffix, currSuffix; int lcpcount; for (var currSuffixIdx = 1; currSuffixIdx < lcp.Length; currSuffixIdx++) { prevSuffix = source.AsSpan(orderedSuffixArray[currSuffixIdx - 1]); currSuffix = source.AsSpan(orderedSuffixArray[currSuffixIdx]); lcpcount = 0; for (int idx = 0; idx < Math.Min(prevSuffix.Length, currSuffix.Length); idx++) { if (prevSuffix[idx] != currSuffix[idx]) break; lcpcount++; } lcp[currSuffixIdx] = lcpcount; } return lcp; } /* INPUT i 1 2 3 4 5 6 7 S[i] b a n a n a @ SUFFIX ARRAY i 1 2 3 4 5 6 7 A[i] 7 6 4 2 1 5 3 1 @ a a a b n n 2 @ n n a a a 3 a a n @ n 4 @ n a a 5 a n @ 6 @ a 7 @ LCP i 1 2 3 4 5 6 7 H[i] - 0 1 3 0 0 2 RESULT a | an ana | anan anana | b ba ban bana banan banana | n na | nan nana ^ */ public static char AshtonString(string source, int targetCharIndex) { var suffixArray = ConstructOrderedSuffixArray(source); var lcp = CalculateLongestCommonPrefix(source, suffixArray); long slength = source.LongCount(); long charCount = 0; //foreach suffix collect all its prefixes and count found characters for (int sufidx = 0; sufidx < slength; sufidx++) { //the character length of processed suffix long suffixLength = slength - suffixArray[sufidx]; //length of longest common prefix between this suffix and previous one int lcplength = lcp[sufidx]; //number of prefixes that can be extracted from current suffix long totalCharCount = suffixLength * (suffixLength + 1) / 2; //exclude duplicate suffixes totalCharCount -= lcplength * (lcplength + 1) / 2; //if kth character of the string is not incuded in this suffix then skip to next suffix if (charCount + totalCharCount < targetCharIndex) { charCount += totalCharCount; continue; } //iterate all prefixes of current suffix //skp Longest Common Prefixes and start from +1 long prefix for (int prefixLength = lcplength + 1; prefixLength <= suffixLength; prefixLength++) { //check if target char is included in this prefix if (charCount + prefixLength >= targetCharIndex) { //if so then return it return source[(int)(suffixArray[sufidx] + (targetCharIndex - charCount - 1))]; } charCount += prefixLength; } } return Char.MinValue; } } class Solution { public static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); int t = Convert.ToInt32(Console.ReadLine().Trim()); for (int tItr = 0; tItr < t; tItr++) { string s = Console.ReadLine(); int k = Convert.ToInt32(Console.ReadLine().Trim()); char res = Result.AshtonString(s, k); textWriter.WriteLine(res); } textWriter.Flush(); textWriter.Close(); } } Ashton and String Java Solution 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(); } } Ashton and String JavaScript Solution 'use strict'; const fs = require('fs'); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', function(inputStdin) { inputString += inputStdin; }); process.stdin.on('end', function() { inputString = inputString.split('\n'); main(); }); function readLine() { return inputString[currentLine++]; } const RADIX = 26; const CVAL = { a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7, h: 8, i: 9, j: 10, k: 11, l: 12, m: 13, n: 14, o: 15, p: 16, q: 17, r: 18, s: 19, t: 20, u: 21, v: 22, w: 23, x: 24, y: 25, z: 26, }; function ord(char) { return CVAL[char] || 0; } function countingSort(alphabetSize, objects, ord) { const count = new Array(alphabetSize).fill(0); const result = new Array(objects.length); for (const o of objects) { count[ord(o)] += 1; } for (let i = 1; i < count.length; i += 1) { count[i] += count[i-1]; } for (let i = objects.length-1; i > -1; i -= 1) { const o = objects[i]; const v = ord(o); result[count[v]-1] = o; count[v] -= 1; } return result; } function radixSort(alphabetSize, objects, orderFields) { let result = objects; for (let f = orderFields.length-1; f > -1; f -= 1) { const ord = (o) => o[orderFields[f]]; result = countingSort(alphabetSize, result, ord); } return result; } function computeRelativeRanks(substringRanks) { let n = substringRanks.length; let relativeRanks = new Array(n); let r = 1; relativeRanks[substringRanks[0].index] = r; for (let i = 1; i < n; i += 1) { const prevRankObj = substringRanks[i-1]; const currRankObj = substringRanks[i]; if ( prevRankObj.leftRank !== currRankObj.leftRank || prevRankObj.rightRank !== currRankObj.rightRank ) { r += 1; } relativeRanks[currRankObj.index] = r; } return relativeRanks; } function computeSuffixArray(string) { const n = string.length; let substringRanks = []; for (let i = 0; i < n; i += 1) { substringRanks.push({ leftRank: ord(string[i]), rightRank: string[i+1] ? ord(string[i+1]) : 0, index: i, }); } substringRanks = radixSort(RADIX+1, substringRanks, ['leftRank', 'rightRank']); let l = 2; // each half's length while (l < n) { let relativeRanks = computeRelativeRanks(substringRanks); for (let i = 0; i < n; i += 1) { const rankObject = substringRanks[i]; rankObject.leftRank = relativeRanks[rankObject.index]; rankObject.rightRank = relativeRanks[rankObject.index+l] || 0; } substringRanks = radixSort(n+1, substringRanks, ['leftRank', 'rightRank']); l = 2*l; } return substringRanks.map(r => r.index); } function computeSuffixRanksFromSuffixArray(suffixArray) { const ranks = new Array(suffixArray.length); for (let i = 0; i < suffixArray.length; i += 1) { ranks[suffixArray[i]] = i; } return ranks; } function computeLCPArray(string, suffixArray) { const n = string.length; const sortedSuffixes = suffixArray || computeSuffixArray(string); const suffixRanks = computeSuffixRanksFromSuffixArray(sortedSuffixes); const lcp = new Array(n).fill(0); let commonLength = 0; for (let i = 0; i < n; i += 1) { const suffixRank = suffixRanks[i]; if (suffixRank > 0) { const currSuffixI = sortedSuffixes[suffixRank]; const prevSuffixI = sortedSuffixes[suffixRank-1]; while (string[currSuffixI+commonLength] === string[prevSuffixI+commonLength]) { commonLength += 1; } lcp[suffixRank] = commonLength; if (commonLength > 0) { commonLength -= 1; } } } return lcp; } function computeContributionScore(length, skip) { return (length*length + length - skip*skip - skip) / 2; } function kLookup(string, skip, k) { const offset = (skip*skip + skip) / 2; k += offset; let s = 0; let n = 1; while (s+n < k) { s += n; n += 1; } k -= s; return string[k-1]; } function ashtonString(s, k) { const n = s.length; const suffixes = computeSuffixArray(s); const lcparray = computeLCPArray(s, suffixes); let suffixIndex = 0; let suffixLength = n - suffixes[suffixIndex]; let suffixScore = computeContributionScore(suffixLength, lcparray[suffixIndex]); while (k > suffixScore) { k -= suffixScore; suffixIndex += 1; suffixLength = n - suffixes[suffixIndex]; suffixScore = computeContributionScore(suffixLength, lcparray[suffixIndex]); } const suffix = s.slice(suffixes[suffixIndex]); return kLookup(suffix, lcparray[suffixIndex], k); } function main() { const ws = fs.createWriteStream(process.env.OUTPUT_PATH); const t = parseInt(readLine().trim(), 10); for (let tItr = 0; tItr < t; tItr++) { const s = readLine(); const k = parseInt(readLine().trim(), 10); const res = ashtonString(s, k); ws.write(res + '\n'); } ws.end(); } Ashton and String Python Solution def foo(text, k): stack = [("",list(range(len(text))))] while stack != []: prefix,ii = stack.pop() if k<len(prefix): return prefix[k] k -= len(prefix) cs = sorted([(text[i],i+1) for i in ii if i<len(text)], reverse=True) i = 0 while i<len(cs): c = cs[i][0] ii2 = [cs[i][1]] j = i+1 while j<len(cs) and cs[j][0]==c: ii2.append(cs[j][1]) j+=1 stack.append((prefix+c, ii2)) i=j return None T = int(input().strip()) for i in range(T): text = input().strip() k = int(input().strip()) print(foo(text,k-1)) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython