This question has been asked to me by Google in Phone Screen Interview. I think this question is of medium difficulty and I am posting here for the community.

Find the shortest substring where all the alphabets (a to z) appear in order. Consider alphabets as case insensitive means 'a' and 'A' are same.

I started with preprocessing the input string by putting frequency of each character in an array where each position of array holds an array list for all the indexes of the characters.

ArrayList [] map = new ArrayList [26];

After this I started with first index of 'a' in map and tried to find index of 'b' which is greater than index of 'a' and so on. At the end I have a substring and I compare the length of substring with minLength variable and update minLength accordingly.

I was able to come up with O(n^2) solution in the given 45 minutes and coded it cleanly.

Can we do it in O(n) time?

Input: str = "...a lot of people, be something, C algha, dghala, edhga, ftuggahaghaiafjgahalhk qafsl agagam afagnasfkhgs Ogahapqrhglaghashlh thgl uqlgha vagagh wagklha xaghhknmbv yaxbvmZ..."

Output: substring which starts with 'a' and end with 'Z'