#[Killjee and k-th letter][1]
Difficulty:Medium
Prerequisite: None
Problem:
Given a string s, answer queries regarding Kth character of Special String generated from given string. You have to answer queries online.
Special String is formed by sorting all sub-strings of given string and concatenating them.
Solution:
Main issue: We have to somehow save the concatenated string. But storing it in a string variable will naturally exceed the memory limit and well as Time Limit for string length upto 10^5.
So, what I did was, I divided the output string into a vector(v) of nodes.
Node struct consist of:
- boolean x: 0 for string repeatation,1 for all substrings
- int l: total length of node
- String s: string to be repeated
- int sp: start point for type 1,no.of times to repeat for type 0.
- int skip: no.of chacters to skip for type 1.
At first, I made an array(a) of lists having the position(s) of each character in the string.
a[0]={all position where ‘a’ occur in given string}
block_a=all substring starting with an ‘a’.
a[1]={all position where ‘b’ occurs in given string}
block_b=all substring starting with a ‘b’.
Now, let’s consider block_a. Let the length of a[0] be l.
It’s guaranteed that there will be at least l ‘a’ in the beginning of string.So, in v[0] we will save this info.(x=0,l=l,s=“a”,sp=l).
Now, the first substring of block b will come after the last substring of block_a.
If we move to the next index for each element in a[0], We are, in a recursive way, left with the same problem(i.e. we need to sort all substring starting from an index in a[0] and all these substrings will have ‘a’ as a prefix(ps)).
Hence, we will go for recursion until the length of the vector passed is reduced to 1.When the length is 1, we will have to print all string starting from that index with prefix(ps).This info. can be stored in a node of type 1(x=1).
Example, say string is “abc”. Then length of a[0] is 1 and a[0][0]=0; This means now all substrings starting from s[0] , i.e. “a” , “ab” , “abc” will have to be appended. This info is now stored only in a single node of type1.
(here, I used the test function to print the final string and check for some inputs).
Now, we can have vector(psum) for the prefix sum of lengths of node.
For, a value of k we can apply binary search to get the node to which it belongs.And within that node, the character can be found easily.
If you have better solution or if you have any doubts feel free to leave a comment below 
Link to my
[2]
Side Note: I did expect TLE for some test cases.I know a test case where my code won't work, don't know how it got passed. :D
[1]: https://www.codechef.com/problems/KILLKTH
[2]: https://www.codechef.com/viewsolution/16779700