Guess the String given Random Triplets
algorithm
Solution
This can happen after calling the random triplet function multiple times.
Suppose our string was "hello"
Let calling random triplet function gives the following on every call but not necessarily in this order:
ell llo hel hlo elo
If I create a graph from the characters I get from the random triplet function:
From this graph, I can only interpret that starting letter may be
'H'
and ending letter may be
'O'
Then if I find the longest path in the graph. I will get "hello" or "olleh" depending upon where I begin from.
Also the number of nodes visited in the path will be equal to the length of the string.
Assumption :
- I could create this graph only after calling random triplet function multiple times.
- Each time I get unique triplets from the random function to construct the graph
Problem
Given an unknown string, execute an utility function, called ``` string returnRandomTripletFromString(string) ``` the function returns a random triplet from the unknown string, you are also given length of the string the random triplet returned by the utility function, would maintain the relative order of letters in string, Lets say the string is helloworld it would return 'hel', 'wod', 'lor' but it would never return 'lhd' since h is before l in the string How can you guess the string using this utility function, using minimum number of calls to the function.