Google | Phone | Substring with all alphabets in sequence

Applied in September 2019, got 2 questions during the call:

  1. (EASY) Write a function that checks if the given String (may contain latin characterz too) has all the alphabets in sequence. Example
sabuycudkge fagkhfgi jakilameng,okpaq reswytgukjvfwgxaeyw z,kg
 ^^  ^ ^  ^ ^ ^ ^  ^ ^ ^ ^ ^ ^  ^ ^ ^ ^ ^  ^ ^  ^ ^ ^  ^  ^

The function returns true.

  1. (HARD) Given a string, find the shortest substring containing all the alphabets in order as subsequence.
    For example:
    Given String : "sabuycudkge fagkhfgi jakilameng,okpaq reswytgukjvfwgxaeyw z,kg asdfjhbsadcdefghijklmnopqrstuvwxy,!z"
    Output : asdfjhbsadcdefghijklmnopqrstuvwxy,!z

I solved the first question at the 10th minute during the call.

The second question took me a while. I couldn't complete the code by the 45th minute and hence got rejected. Please share your approach for solution 2.

I used sliding window but couldn't get to an optimized solution.

Comments (8)