I was asked this question today:

given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n]

IF we sort the valid substrings alphabetically, what will be the first one and what will be the last one?

If we do need to sort all the substrings, then we might need a suffix tree or suffix array. However, here we do not need to sort --- we don't care all the substrings except the first and last one. So I am wondering if there is any more efficient solution than using suffix array.



1 Answer 1


Find the last occurence of any h, i, j, k, l, n. If none is found, there is no solution. If the last one is found at position r, then the string we are looking for must start at position before r.

Then you start from the left looking for the first letter among a, b, c, d, e. If you don't find one before position r then there is no solution. Otherwise call this index l; the first string in the alphabet might start at index l.

Look further for more characters starting with a to e. If you find one at position l', you then find the first difference between the string starting at l and l', up to and including position r. If there is a different character, and the first character in the string starting at l' is earlier in the alphabet, replace l with l'.

Finally, the first string in the alphabet is the one starting at position l, and up to and including the first letter in 'h' to 'n'.

PS Re-reading this after more than a year there may be some more or less subtle bugs in this code, but it is roughly right.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.