Recently, somebody posted a problem that was asked in his Google Phone Interview. The first problem was easy and could be solved with an O(n) algorithm.
1. Find out if a string contains all alphabet characters in their respective order.
For example:
sabuycudkge fagkhfgi jakilameng,okpaq reswytgukjvfwgxaeyw z,kg
^^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
output: true
The idea is just to go through each character and maintain an incrementing counter. If ever ctr reaches 26, then we know we’ve reached the z’th character and we can return true. Otherwise, return false;
public boolean solve(String s){
int ctr = 0;
for(int i=0; i < s.length(); i++){
int current = s.charAt(i) - 'a';
if(current == ctr){
ctr++;
}
if(ctr == 26) return true;
}
return false;
}
The second problem is an optimization problem where we have to find the shortest substring which contains all the alphabet in their respective order.
2. Find the minimum substring that contains all the alphabet in their respective order.
For example:
sabuycudkge fagkhfgi jakilameng,okpaq reswytgukjvfwgxaeyw z,kg asdfjhbsadcdefghijklmnopqrstuvwxy,!z
Output: asdfjhbsadcdefghijklmnopqrstuvwxy,!z
At first, you would think that the solution for #1 can be reused. This is possible but then that means your algorithm would run O(n^2) because you would then now have to traverse each character again and again to check if your ctr would reach 26.
A more optimized way is by maintaining an array which will contain the index of ‘a’ when a particular character was found in the input string.
public String solve2(String s){
int[] alphabet = new int[26];
Arrays.fill(alphabet, -1);
int start = 0; int end = Integer.MAX_VALUE;
for(int i=0; i < s.length(); i++){
int ch = s.charAt(i) - 'a';
// if this isn't part of alphabet, skip
if(ch < 0 || ch > 25) continue;
// once we've seen a 'z' character, check if the diff of current index and
// index of 'y' is less than the current range (end - start) and update
// the range accordingly.
// the confusing part here is that, the y'th index is not really its position
// but rather the position of 'a' when this 'y' was found.
if (ch == 25 && alphabet[24] != -1 && i+1-alphabet[24] < end-start) {
start = alphabet[24]; end = i+1;
}
alphabet[ch] = ch == 0 ? i : alphabet[ch - 1];
}
return end==Integer.MAX_VALUE ? "" : s.substring(start, end);
}