Find the longest occurrence of the "aeiou" in a string

Question

I was recently doing an interview and was asked multiple questions, one of the questions was this and I had a bit of trouble trying to answer it.

Given a string, find the longest occurrence of vowels "aeiou" that appear. The substring of vowels do not have to be consecutive, and there can be repeats.

The goal is the find the max occurrence of each vowel and join them, but it must be in the order of "a","e","i","o","u".

Edit: In addition, each individual vowel character must be chained as well. In the example below, there is "aaa" and "aa" , since 3 is longer, our result must contain the longer chain.

For example: Input: "aaagtaayuhiejjhgiiiouaae" Result: aaaeiiiou

The code that I have tried is below:

EDIT: Following the solution, I have written this below but I am still running into issues with strings such as "aeiouaaaeeeiiiooouuu". The correct result for that would be 15 but I am getting 5.

var findLongestVowels = function(s){
var count = 1;
var i = 0; 
var j = 0;
var vowels = ['a','e','i','o','u'];
var total = 0; 
var array = [];
while (i < s.length){
    if (s.charAt(i) == vowels[j] && s.charAt(i) == s.charAt(i+1) ){
        count++;
    }
    else if (s.charAt(i) == vowels[j] && s.charAt(i) != s.charAt(i+1)){
        if (j === 0 && !array[vowels[j]]){
            array[vowels[j]] = count;
        }
        else if (j === 0 && array[vowels[j]]){
            array[vowels[j]] = Math.max(array[vowels[j]],count);
        }
        else if (j !== 0 && !array[vowels[j]] && array[vowels[j-1]]){
            array[vowels[j]] = array[vowels[j-1]] + count;
        }
        else if (j !== 0 && array[vowels[j]] && array[vowels[j-1]]){
            array[vowels[j]] = Math.max(array[vowels[j]],array[vowels[j-1]] + count);
        }
      count = 1; 
    }
    else if (s.charAt(i) == vowels[j+1] && array[vowels[j]]){
        j++;
        i--;
    }
    i++;
  }
  console.log(array);
  console.log('Answer: ' + array[vowels[j]]);
}

findLongestVowels("eeeeebbbagtaagaaajaaaaattyuhiejjhgiiiouaae");

Am I at least going in the right direction?

Thanks in advance.

Answer 1

We can solve this in O(n) time. Consider that for each block, if its vowel is at index v in the list of vowels, we are only interested in the best solution for the block with a vowel at index v-1 in the order of vowels. We save the last best solution for each block type (each vowel) as we go along:

   |aaa|g|t|aa|y|u|h|i|e|jj|h|g|iii|o|u|aa|e
b:  1       2    3   4 5        6   7 8 9  10

b 1: v[a] = 3
b 2: v[a] = max(2,3)
b 3: v[u] = None recorded for v-1
b 4: v[i] = None recorded for v-1
b 5: v[e] = 1 + 3
b 6: v[i] = 3 + 4
b 7: v[o] = 1 + 7
b 8: v[u] = 1 + 8 // answer 
b 9: v[a] = max(2,3)
b 10: v[e] = 1 + 3

JavaScript code:

function f(str){
  console.log(`String: ${ str }\n`);
  
  var vowels = {
    a: {best: 0, prev: null},
    e: {best: 0, prev: 'a'},
    i: {best: 0, prev: 'e'},
    o: {best: 0, prev: 'i'},
    u: {best: 0, prev: 'o'}
  };
  
  function getBlock(i){
    let length = 1;
    
    while (str[i+1] && str[i] == str[i+1]){
      length++;
      i++;
    }
      
    return length;
  }
  
  for (let i=0; i<str.length;){
    let length = getBlock(i);
    
    console.log(`i: ${ i }; length: ${ length }`)
    
    if (!vowels[str[i]]){
      i = i + length;
      continue;
    }
    
    if (!vowels[str[i]].prev){
      vowels[str[i]].best = Math.max(
        vowels[str[i]].best,
        length
      );
      
    // make sure the previous vowel
    // exists in the string before
    // this vowel
    } else if (vowels[ vowels[str[i]].prev ].best){
      vowels[str[i]].best = Math.max(
        vowels[str[i]].best,
        length + vowels[ vowels[str[i]].prev ].best
      );
    }
    
    i = i + length;
  }
  
  console.log(`\n${ JSON.stringify(vowels) }\n\n`);
  
  return vowels['u'].best;
}

var s = 'eeeeebbbagtaagaaajaaaaattyuhiejjhgiiiouaae';
console.log(f(s) + '\n\n');

s = 'aaagtaayuhiejjhgiiiouaae';
console.log(f(s) + '\n\n');

s = 'aeiouaaaeeeiiiooouuu';
console.log(f(s));

Answer 2

This problem can be solved by using dynamic programming technique.

First, we have string x and we want to find the longest string for this string.

Traversing the string x from start to end, assuming at index i, we are trying to find vowel e, there are two possibilities:

• Current character is e, so we take the whole block and move to next character
• Or, we can try with the next character

So, we have our pseudocode:

int[][]dp;
int largestBlock (int index, int currentVowel, String x, String vowels){
    if (currentVowel == 5) {
       // We found all 5 vowel
       return 0;
    }
    if visited this state (index, currentVowel) before {
       return dp[index][currentVowel]; 
    }
    int result = largestBlock(index + 1, currentVowel, x, vowels) ;
    if (x[index] == vowels[currentVowel]){
        int nxt = nextIndexThatIsNotVowel(index, currentVowel, x, vowels);
        result =  max(result, nxt - index + largestBlock(nxt, currentVowel + 1, x , vowels));        
    }
    return dp[index][currentVowel] = result;
} 

Time complexity is O(n * m) with m is number of vowels which is 5 in this case.