Find the longest appearance of "aeiou" in the string

Question

I recently did an interview and asked several questions, I had one of the questions, and I had few problems trying to answer it.

Given the string, find the longest appearance of the aeiou vowels that appear. The vowel substring does not have to be consistent, and there may be repetitions.

The goal is to find the maximum appearance of each vowel and join them, but it should be in the order of "a", "e", "i", "o", "u".

Edit: In addition, each individual vowel symbol must also be chained. In the example below, there are "aaa" and "aa", since 3 is longer, our result should contain a longer chain.

For example: Input: "aaagtaayuhiejjgiiiouaae" Result: aaaeiiiou

The code I tried is below:

EDIT: after the solution, I wrote this below, but I'm still having problems with strings like "aeiouaaaeeeiiiooouuu". The correct result for this would be 15, but I get 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 in index v in the list of vowels, we are only interested in the best solution for a block with a vowel with index v-1 in the vowel order. We keep the last best solution for each type of block (each vowel) as we move:

  |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 using the dynamic programming method.

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

Moving the string x from beginning to end, assuming in index i , we are trying to find the vowel e , there are two possibilities:

• The current character is e , so we take the whole block and move on to the next character
• Or we can try the following character

So, we have our pseudo code:

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

The time complexity is O (n * m), where m is the number of vowels, which in this case is 5.

Answer 3

You need to remember the largest combination 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 ); 

Answer 4

This is just one of many possible solutions - feel free to try.

• Store each vowel that interests you in the vowels array.
• Use map to cycle each vowel into an array, create a regular expression from the vowel to split the string into an array of vowels. For example, "aaabdmedaskaa" will be divided into ["aaa", "a", "aa"] .
• Filter this array so that it does not include blank lines.
• Sort by length, so adding an element of 0 will give you the highest probability
• After matching each vowel, return the result - filter out "undefined" if some of your vowels do not occur at all, and the regular expression leads to an empty array (using an empty array, the 0th element will lead to undefined ), combine the array of events into a result line.

A regular expression 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")); 

Answer 5

Why not regex?

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

Answer 6

First of all, from what I understand from the question, the result for Input: "aaagtaayuhiejjgiiiouaae" should be aaaaaeiiiou, as @PhamTrung asked in the comments, but did not receive an answer.

Since this is a job interview, I would start with the first thing that comes to mind, namely, from the brute force of the decision from 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 one has a terrible runtime, we try to use all possible substring that contains only vowels, than we discard those that do not have the required shape (a + e + i + o + u +), but select only the largest of them. If I'm not mistaken, this has the worst case of Σ (n picks i), which is O (n ^ n) - well, in the worst case, there would be a stackOverflow exception for a sufficiently large n, in which case we would have to override this loop instead of recursion. In this case, we could still get an exception from memory, and in this case we would have no options but to improve our algorithm. It is fair to assume that if the input was large enough to receive an exception from memory, our code would also be slow enough not to be a reasonable solution to the problem. I’m just arguing about all this because this is what the interviewer might want to see that you know, which means that you know enough CS 101.

After that, the interviewer asked if I could improve performance. This is a runtime solution 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 problem with a long trajectory , basically you run through the line and every a indicates the next occurrence of a and the next occurrence of e . e indicates the next e and the next i , etc. You should have a start node pointing to each a and end node visibility that all u events point to. Now you need the longest path from the beginning of the node to the end of the node, which is O (| V | + | E |), now | V | <= n and | E | <= 2n since each node on your graph has no more than 2 vertices, so the total runtime is O (n). I simplified the code for constructing the result when it goes on plotting, 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.

Please note that this solution is based on the assumption that the input string is one that necessarily has a solution built into it. If the input string is unsolvable (it does not contain the aeiou sequence), then this case should be handled correctly, in fact, it is trivial to add code that processes this. The first solution will return null in this case (if I'm not mistaken)

Hope this helps.