How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n] 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.
Thanks
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'.