I have a suffix array. How to get a string, which suffix array will be equal to the given array?
For example. Let I have this array: [7, 6, 4, 2, 1, 5, 3]. Then the string banana$ is good for me, since get_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3].
You could build a directed graph from the constraints, then run Topological Sorting, and assign letters to the nodes according to the resulting order.
Start by constructing nodes for the unknown letters, one for each (except for the $).
The first entry will always be the length of the array, because it is $. This gives us nothing.
The following entries, though, each give us constraints.
For example, since the second entry is the length of the array minus one, it must not be larger than any of the other letters. So place an edge from the this node to each of the others. If, however, it would be the length of the array minus two, then there would be a letter smaller than it, but it would be smaller than all the other ones. You can find which is this smaller element from the suffix array, and place a node from it to the last letter, and from the last letter to all the other letters, etc.
bapapa$has the same array.