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");

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.

• javascript
• node.js
• string
• algorithm

• What if the string is aaeagtaayuhiejjhgiiiouaae? – Rajesh Commented Mar 1, 2018 at 9:58
• 2 For example: Input: "aaagtaayuhiejjhgiiiouaae" result: aaaeiiiou.... why noy 5 a?? – Jordi Castilla Commented Mar 1, 2018 at 9:58
• 1 console.log('aaagtaayuhiejjhgiiiouaae'.match(/[aeiou]+/gi).reduce((a, b) => a.length > b.length ? a : b)); – Tushar Commented Mar 1, 2018 at 10:02
• 2 @Veve As the code is not working as expected, it cannot be migrated to CR.SE. – Tushar Commented Mar 1, 2018 at 10:28
• 1 @PhamTrung your code returns 12 for "eioeeeiiiooouuu" but there's no 'a' :) – גלעד ברקן Commented Mar 2, 2018 at 12:21

7 Answers 7

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));

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 plexity is O(n * m) with m is number of vowels which is 5 in this case.

You need to remember biggest bination of individual vowels.

Use reduce, map and Object.values

var vowels = "aeiou";
var input = "aaagtaayuhiejjhgiiiouaae";

var output = Object.values( 
  input.split( "" ).reduce( ( a, c, i, arr ) => {
     var lastChar = arr[ i - 1 ];
     if ( !vowels.includes( c ) ) return a; //if not vowel, return accumulator
     if ( c != lastChar ) //if not same as last character then create a new array
     {
         a[ c ] = a[ c ] || [];
         a[ c ].push( [ c ] );
     }
     else //else push to the last array;
     {
         var lastCombo = a[ c ].slice( -1 )[ 0 ];
         lastCombo.push(c)       
     }
     return a; //return accumulator
  } , {}) ).map( s => {
     var char = s[0][0]; //find the character to repeat
     var maxLength = Math.max.apply( null, s.map( s => s.length ) ); //find how many times to repeat
     return Array( maxLength + 1 ).join( char ); 
  }).join( "" ); //join all the vowels
  
console.log( output );

It's just one of many possible solutions - feel free to try it out.

1. Store every vowel you're interested in, in vowels array.
2. Use map to loop over every vowel in array, create regex from vowel to split string into array of vowels. For example "aaabdmedaskaa" would be split into ["aaa", "a", "aa"].
3. Filter this array so it doesn't include empty strings.
4. Sort it by length, so accesing 0 element would give you longest occurance
5. After mapping over every vowel, return the result - filter out "undefined" in case some of your vowels don't occur at all and regex results in empty array (accesing empty array's 0th element would result in undefined), join array of occurances into a result string.

The regex created from "a" will be [^a]+ which means any character sequence that does not include "a".

function findLongestOccurance(str) {
  const vowels = ["a", "e", "i", "o", "u"];
  const result = vowels.map(vowel => {
    const regex = new RegExp(`[^${vowel}]+`);
    return str.split(regex)
       .filter(r => r !== "")
       .sort((a, b) => b.length - a.length)[0];
  });
  return result.filter(occ => typeof(occ) !== "undefined").join("");
}

console.log(findLongestOccurance("aaagtaayuhiejjhgiiiouaae"));

Why not regex?

var result = /(a+).*(e+).*(i+).*(o+).*(u+)/.exec("aaagtaayuhiejjhgiiiouaae");
console.log(result[1]+result[2]+result[3]+result[4]+result[5]);

First of all, from what I understand from the question the result for Input: "aaagtaayuhiejjhgiiiouaae" should be aaaaaeiiiou, like @PhamTrung asked in the ments but didn't get answered.

Because it a job interview I would start with the first thing that es to mind, namely brute force the solution out of this

function a(string, prefix='') {
    if(!string.length){
        return prefix
    }
    if(!/[aeiou]/.test(string[0])){
        return a(string.substr(1), prefix)
    }
    const option1 = a(string.substr(1), prefix)
    const option2 = a(string.substr(1), prefix+string[0])
    const validateRegex = /^a+e+i+o+u+$/
    
    const isValidOption1 = validateRegex.test(option1)
    const isValidOption2 = validateRegex.test(option2)
    if(isValidOption1 && isValidOption2){
        if(option1.length > option2.length) {
            return option1
        }
        return option2
    }
    if(isValidOption1) {
        return option1
    }
    if(isValidOption2) {
        return option2
    }
    return null
}
const input = 'aaagtaayuhiejjhgiiiouaae'
console.log(a(input))

This has a terrible run time though, we are trying all possible substring that contains only vowels, than we are discarding those that aren't of the form required (a+e+i+o+u+) and than choosing only the biggest of them all. If I'm not mistake this has a worst case of ∑(n choose i) which is O(n^n) - well, the actual worst case here would be a stackOverflow exception for sufficiently large n in which case we'd have to reimplement this with a loop instead of recursing. In this case we could still get an out of memory exception in which case we'd be out of options but to improve our algorithm. It's fair to imagine that if the input were large enough that we got an out of memory exception than our code would also be slow enough to not be a reasonable solution to the problem. I'm just arguing all this because these are things that an interviewer would possibly like to see that you are aware of, meaning you know enough of CS 101.

Following that the interviewer would ask if I can improve the performance. This is a solution with running time of O(n).

const input = 'aeiouaaaeeeiiiooouuu'
let curr = { "1": {price: -1} }
const nodes = []
const voewels = '1aeiou'
const getPrevLetter = (node) => voewels[voewels.indexOf(node.letter) -1]
let resultNode
function setUpNodeByCurrent(node, letter){
    node.price = curr[letter].price + 1
    node.previous = curr[letter]
}
function setBestResultIfNeeded(node){
    if(node.letter !== 'u') {
        return
    }
    if(!resultNode || resultNode.price < node.price) {
        resultNode = node
        return
    }
}
function setCurrent(letter){
    const node = {
        letter,
        price: 0
    }
    const prevLetter = getPrevLetter(node)
    if(!prevLetter || !curr[prevLetter]){
        // either letter isn't on of aeiou or
        // we got to an i without ever seeing an e, an o without ever seeing an i, ... this letter is irrelevant 
        return
    }
    if(curr[node.letter]) {
        setUpNodeByCurrent(node, node.letter)
    } 
    if(node.price < curr[prevLetter].price + 1) {
        setUpNodeByCurrent(node, prevLetter) 
    }
    curr[node.letter] = node
    setBestResultIfNeeded(node)
}
function getStringResult(node){
    let result = ''
    while(node) {
        result = node.letter + result
        node = node.previous
    }
    return result
}
function getResult(){
    const node = resultNode //getBestResultNode()
    const result = getStringResult(node)  
    console.log(result)   
    console.log(result.length)
}
for(let l of input){
    setCurrent(l)
}
getResult()

This can be seen as a simplification of the longest path problem over a DAG basically you'd run through the string and every a points to the next occurance of a and the next occurance of e. e points to the next e and to the next i and so on. You'd than have a start node pointing to every occurance of a and an end node pointed to by every occurance of u. Now what you want is the longest path from the start node to the end node which is an O(|V|+|E|), now |V|<=n and |E|<=2n since every node in your graph has at most 2 vertices going out of it so the total running time is O(n). I have simplified the code to build the result as it goes on building the graph, basically I already calculate the cost on the go so when I finished building a graph similar to what I described I already know what the result is.

Note that this solution is based on the assumption that the input string is one that necessarily has a solution embedded in it. If the input string is unsolvable (there isn't and aeiou sequence in it) than this case would need to be properly handled, it is actually trivial to add the code that handles that. The first solution will return null in such a case(if I'm not mistaken)

Hope this helps.

If you want to find a substring which contains the maximum number of vowels and you also want to give {specify} the length of the substring then you should use this program:

    let newk = s;
    const elementsArray = [];
    const tempoArray = [];
    const counting = [];
    const maxPoint = [];

    let count
    for (var i = 0; i < newk.length; i++) {
        while (tempoArray.length > 0) {
            tempoArray.pop();
        }
        let fk = i + k;
        if (fk <= newk.length) {
            for (let j = i; j < fk; j++) {
                tempoArray.push(newk[j]);
            }
            let makingArray = tempoArray.toString();
            elementsArray.push(makingArray);
        } else {
        //    console.log(" ");
        }
    }


    for (let q = 0; q < elementsArray.length; q++) {
            count = 0
            let tempString = new String(elementsArray[q]).split(",")

            for (let l = 0; l < tempString.length; l++) {
                if (tempString[l] == "a" || tempString[l] == "e" || tempString[l] == "i" || tempString[l] == "o" || tempString[l] == "u") {
                    count ++;
                }else{
                }
            }   
            // console.log(count);
            counting.push(count)        
    }
    let max = 0,Maximist
    // for (let d = 0; d < counting.length; d++) {
    //     console.log(counting[d] , "  this is the value of the counting array");
    // }
    for (let t = 0; t <= counting.length; t++) {
        if (counting[t] != 0) {
            
            if (max < counting[t]) {
                max = counting[t]
                Maximist = t
            }
            else if (max == counting[t]){
                max = counting[t]
                Maximist = t
        }
        else{
            console.log("");
        }
    }
    }
    // console.log(Maximist);
    // console.log(max);
    // maxPoint.push(Maximist)
    for (let t = 0; t <= counting.length; t++) {
        if (counting[0] != 0) {
            if (max == counting[t]) {
                maxPoint.push(t)
            }
        }
    }
    for (let e = 0; e < maxPoint.length; e++) {
        console.log("{", elementsArray[maxPoint[e]] ,"}")        
    }
}
findSubstring("captainamerica", 3);

The bigger your size of the substring will be the less chances that there will be less substring with same number of vowels in it