I am trying to write such an algorithm in Java. I am testing the String input "abaab". It's safe to assume the string inputs will be lowercase.
I am at a loss in checking where my algorithm is going wrong (it only outputs "a a" for this input instead of "ab" and "abaab". Any ideas?
static void SmallestAndLargestSubstring(String input) {
char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x',
'y', 'z' };
char[] charArray = input.toLowerCase().toCharArray();
int startIndex = 0;
int shortEndIndex = 0;
int longEndIndex = 0;
int large = longEndIndex - startIndex;
int small = shortEndIndex - startIndex;
ArrayList<Integer> start = new ArrayList<Integer>();
ArrayList<Integer> end = new ArrayList<Integer>();
outerloop: for (int i = 0; i < charArray.length; i++) {
for (int z = 0; z < vowels.length; z++) {
if (charArray[i] == vowels[z]) {
startIndex = i;
start.add(startIndex);
if (longEndIndex - startIndex > large) {
large = longEndIndex - startIndex;
}
if(longEndIndex - startIndex <= large){
shortEndIndex=start.get(start.size()-1);
}
if (shortEndIndex - startIndex < small) {
small = shortEndIndex - startIndex;
}
if(shortEndIndex - startIndex >=small){
shortEndIndex=start.get(start.size()-1);
}
continue outerloop;
}
}
for (int j = 0; j < cons.length; j++) {
if (charArray[i] == cons[j]) {
longEndIndex = i;
shortEndIndex = i;
end.add(longEndIndex);
if (longEndIndex - startIndex > large) {
large = longEndIndex - startIndex;
}if(longEndIndex - startIndex <= large){
longEndIndex=end.get(end.size()-1);
}
if (shortEndIndex - startIndex < small) {
small = shortEndIndex - startIndex;
}
if(shortEndIndex - startIndex >=small) {
shortEndIndex=end.get(end.size()-1);
}
continue outerloop;
}
}
}
System.out.println(input.substring(startIndex, shortEndIndex));
System.out.println(input.substring(startIndex, longEndIndex));
}
Here is my solution : the longest substring always start with the first vowel and end with the last consonant. For the shortest, every time I read a consonant, I look at the distance to the previous vowel and see if it is better. You can't do anything until you read at least one vowel.
static void SmallestAndLargestSubstring(String input) {
char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x',
'y', 'z' };
char[] charArray = input.toLowerCase().toCharArray();
int longStartIndex=0;
int shortStartIndex=0;
int shortEndIndex=0;
int longEndIndex=0;
boolean findVowel = false;
int bestStart = 0;
int bestEnd = 0;
int shortest =Integer.MAX_VALUE;
for (int i = 0; i < charArray.length; i++) {
for (int z = 0; z < vowels.length; z++) {
if (charArray[i] == vowels[z]) {
if (!findVowel){
// if this is the first vowel we see
longStartIndex = i;
shortStartIndex=i;
findVowel = true;
}
else {
shortStartIndex = i;
}
}
}
for (int j = 0; j < cons.length; j++) {
if (charArray[i] == cons[j]) {
if (findVowel){
// if we have seen any vowel, this consonant is useless
longEndIndex = i; // this one is always than the previous for the largest
shortEndIndex = i; // we have to check if this one is better or not
if (shortEndIndex-shortStartIndex<shortest){
bestStart = shortStartIndex;
bestEnd = shortEndIndex;
shortest = shortEndIndex-shortStartIndex;
}
}
}
}
}
System.out.println(input.substring(bestStart, bestEnd+1));
System.out.println(input.substring(longStartIndex, longEndIndex+1));
}