Certain letters of the alphabet are “lucky”. The first “lucky” letter of the alphabet is “a”, and every 2nd letter after a is also considered “lucky”. In this way lucky letters include “a”, “c”, “e”, “g” … etc. The alphabet consists of the lowercase letters a-z.
A word is considered “lucky” if it contains at least 4 “lucky” characters e.g. “asks”. Given an Array of N Strings (where each string contains a sentence) write a class which can print out the 2 “luckiest” sentences where “luck” is measured by the number of “lucky” words in the sentence. The goal is to write the most efficient algorithm, optimizing for both space and time. Briefly discuss the computational complexity of your solution.
Example:
Input {“once upon a midnight dreary”, “say aaaaah for the dentist”, “lima is in peru”, “three blind mice see how they run”}
Output:
once upon a midnight dreary
say aaaaah for the dentist
Here is the naive algorithm:
public class Main {
public int countLuck(String s) {
char[] a = s.toCharArray();
int luck = 0;
int count = 0;
for (int i = 0; i < a.length; ++i) {
if (a[i] == ' ') {
if (count >= 4)
++luck;
count = 0;
}
else if (((int)(a[i] - 'a')) % 2 == 0)
++count;
}
return luck;
}
public void luckiest(String[] a) {
int[] c = new int[a.length];
int max1 = -1;
for (int i = 0; i < a.length; ++i) {
c[i] = countLuck(a[i]);
if (max1 < 0)
max1 = i;
else if (c[i] > c[max1])
max1 = i;
}
System.out.println(a[max1]);
int max2 = -1;
for (int i = 0; i < a.length; ++i) {
if (i == max1)
continue;
if (max2 < 0)
max2 = i;
else if (c[i] > c[max2])
max2 = i;
}
System.out.println(a[max2]);
}
public static void main(String[] args) {
Main obj = new Main();
String[] arr = {"once upon a midnight dreary", "say aaaaah for the dentist", "lima is in peru", "three blind mice see how they run"};
obj.luckiest(arr);
}
}
2 Likes
There’s a bug here.
When you say "a[ i ] == ’ ’ ", you do not consider the last word in the String because there is no space at the end of the String.
I suggest using a StringTokenizer to break up the String into the individual words.
i agree with the solution 
even it is not necessary just check the character by character and if character is a letter then calculate whether it is lucky number or not otherwise go on next character if its ’ ’
tijoforyou’s solution is incorrect in the countLuck method. There is a bug there. When he uses a[ i ] == ’ ’ to determine if a word has finished, he leaves out the last word of every String because there is no white space after the last word.
To prove my point about tijoforyou’s solution as incorrect, it does not work for the test case: “aaaa aaaa aaaa bbbb”, “aaaa aaaa aaaa aaaa”, “aaaa aaaa aaaa aaac”. The first String has 3 lucky words whereas the last two have 4 each. The correct output should be, therefore, the last two Strings. However, after running this on my computer, tijoforyou’s solution outputs the first two Strings instead. This is because it does not consider the last word of each sentence.
My countLuck method would be like this:
public int countLuck( String s ) {
int luck = 0;
StringTokenizer tokens = new StringTokenizer( s );
while( tokens.hasMoreTokens() ) {
String temp = tokens.nextToken();
int count = 0;
for( int i = 0; i < temp.length(); i++ ) {
if( (int)( temp.charAt( i ) - 'a' ) % 2 == 0 )
count++;
}
if( count >= 4 )
luck++;
}
return luck;
}
3 Likes
To prove my point about this solution being incorrect, try this with the test case: “aaaa aaaa aaaa bbbb”, “aaaa aaaa aaaa aaaa”, “aaaa aaaa aaaa aaac”. The first String only has 3 lucky words whereas the last two strings both have 4. Therefore, the correct output should be the 2nd and the 3rd String. However, after running this on my computer, it outputs the first and the second String because it does not consider the last word of the whole sentence.
yup @kullalok there is a problem there …i agree with ur solution
Yeah! That is right! Thanks guys for pointing out the mistake.
Did a quick naive pgm. Didn’t give much thoughts on that. Got to be careful from now. 
What about the your solution’s complexities?
What would you use to test this code?
What is the string tokenizer actually doing under the hood?
How can you do this with fewer instruction? At least try to impress…
Improve this: else if (((int)(a[i] - ‘a’)) % 2 == 0)