Guess the String given Random Triplets

Question

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.

Answer 1

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 :

1. I could create this graph only after calling random triplet function multiple times.
2. Each time I get unique triplets from the random function to construct the graph

Answer 2

I'm treating 'bok' as disallowed in your example.

in general it can be very difficult, suppose the target string was "10101010" them all possible substring are possible, if it is known what bias the random function which picks the triplets has it may be possible to use statistical analysis to deconvolve the distribution of yielding the original

one approach cpuld be 1 determine which characters comprise the string, 2 try different combinations of those characters until you find one that yields a similar distribution of results.

the statistical rules that govern the proportions od each result are a system of linear equations so it may be possible to attempt a simultaneous solution to these equations