I'm currently trying to figure out whether a given array, which is a permutation of the numbers 1 to n, is a suffix array of any binary string.
For example for n = 3, A = {2, 1, 3} is valid, since there exists the binary string [101] with [01] < [1] < [101] (using lexicographical ordering). However {2, 3, 1} is not a valid suffix array, as there is no binary string for which the lexicographical order holds.
My current approach simply enumerates all binary strings of length n, and checks whether the suffix array is correctly ordered w.r.t. each string. This is obviously rather slow, as there are 2^n candidate binary strings to be checked in O(n) each.
The obvious approach to this kind of problem would be to look for similarities in the valid suffix arrays, however I've thus far only been able to deduce one property:
If A is a valid suffix array for a binary string, then prefixing A with 1 and incrementing all values of A yields a valid suffix array as well.
This property however does not help me with suffix arrays that do not start with 1, when attempting to validate them.
