在字符串中找到最长的“aeiou”出现次数

Question

最近我参加了一次面试，被问到了多个问题，其中一个问题是这个，我在回答时遇到了一些困难。

给定一个字符串，找到出现的元音字母"a,e,i,o,u"的最长连续子串。 元音字母的子字符串不必是连续的，并且可以重复。

目标是找到每个元音字母的最大出现次数并将它们连接起来，但必须按照"a"，"e"，"i"，"o"，"u"的顺序进行。

编辑：此外，每个单独的元音字符也必须被链接。 在下面的示例中，有"aaa"和"aa"，因为3更长，所以我们的结果必须包含更长的链。

例如： 输入："aaagtaayuhiejjhgiiiouaae" 输出：aaaeiiiou

我尝试过的代码如下：

编辑：根据解决方案，我写了下面的代码，但是我仍然遇到了字符串“aeiouaaaeeeiiiooouuu”等字符串的问题。 正确的结果为15，但我得到的是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");

我至少走在正确的方向上吗？

提前感谢。

- Leo Li

---

例如：输入：“aaagtaayuhiejjhgiiiouaae” 结果：“aaaeiiiou”。为什么没有5个“a”？ - Jordi Castilla

console.log('aaagtaayuhiejjhgiiiouaae'.match(/[aeiou]+/gi).reduce((a, b) => a.length > b.length ? a : b)); - Tushar

@Veve 由于代码未按预期工作，无法迁移到CR.SE。 - Tushar

嗯，你的代码看起来过于复杂了。你可以看一下我的Java代码。 - Pham Trung

@PhamTrung，你的代码对于“eioeeeiiiooouuu”返回12，但是没有字母'a' :) - גלעד ברקן

Answer 1

我们可以在O(n)的时间内解决这个问题。考虑到每个块，如果它的元音字母在元音字母列表中的索引是v，那么我们只对元音字母在元音列表中索引为v-1的块（按照元音字母顺序）的最佳解决方案感兴趣。我们沿途保存每种块类型（每个元音字母）的最后一个最佳解决方案：

   |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 代码：

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

- גלעד ברקן

---

你能详细解释一下你的算法，或者提供一些代码吗？我刚试着按照那种方式实现了它，对于除了这种情况“aeiouaaaeeeiiiooouuu”之外的每种情况都成功了，但是使用它我得到的结果是5，而不是应该得到的15，我错过了什么吗？ - Leo Li

@PhamTrung，我刚刚编辑了问题，并根据解决方案编写了新代码。 - Leo Li

@LeoLi 添加了代码。（请注意，片段查看器中的控制台日志有时会被截断。在其他地方运行代码以完整查看控制台日志。） - גלעד ברקן

谢谢@גלעדברקן！！这非常有帮助，肯定帮助我学到了很多！ - Leo Li

@LeoLi 如果您认为问题已经得到了令人满意的回答，请随意接受适当的答案（点击答案投票旁边的复选标记），这样其他人就会知道它已经解决 :) - גלעד ברקן

Answer 2

这个问题可以通过使用动态规划技术来解决。

首先，我们有字符串 x，我们想找到该字符串的最长子串。

遍历从头到尾的字符串 x，假设在索引 i 处，我们正在尝试查找元音字母 e，有两种可能：

当前字符是 e，所以我们取整个块并移动到下一个字符

或者，我们可以尝试下一个字符

因此，我们有以下伪代码：

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

时间复杂度为 O(n * m)，其中 m 是元音字母的数量，本例中为 5。

- Pham Trung

---

发布了O(n)的解决方案 :) （还点赞了+1） - גלעד ברקן

Answer 3

你需要记住单个元音字母的最大组合。

使用 reduce、map 和 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 );

- gurvinder372

Answer 4

这只是许多可能的解决方案之一 - 随意尝试。

1. 将您感兴趣的每个元音存储在vowels数组中。
2. 使用map循环遍历数组中的每个元音，从元音创建正则表达式以将字符串拆分为元音数组。例如，“aaabdmedaskaa”将被拆分为["aaa", "a", "aa"]。
3. 过滤此数组，使其不包含空字符串。
4. 按长度排序，因此访问0元素将给您最长的出现次数。
5. 在映射每个元音后，返回结果 - 过滤掉“undefined”，以防某些元音根本不出现，并且正则表达式导致空数组（访问空数组的第0个元素将导致undefined），将出现的数组连接成结果字符串。

从“a”创建的正则表达式将是[^a]+，表示不包括“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"));

- Tomasz Bubała

---

您的代码在针对包含“iii”和“oooo”的字符串“aaagtaayuhiejjhgooooiiiouaae”进行计算时返回了答案。除非我误解了问题，否则所选块应按照它们在字符串中出现的顺序排列，是吗？ - גלעד ברקן

根据问题中的示例逻辑：“例如：输入：“aaagtaayuhiejjhgiiiouaae”结果为：aaaeiiiou” - 这是期望输出。 除非我误解了问题，否则传递“aaagtaayuhiejjhgooooiiiouaae”应该会导致“aaaeiiioooou”。 - Tomasz Bubała

这似乎是一个非常琐碎的问题 :) 只需加入字符串中任何位置找到的每个元音字母的最大块即可。 - גלעד ברקן

这只是我的理解 - 我想只有 OP 能回答。 - Tomasz Bubała

Answer 5

为什么不用正则表达式呢？

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

- Thomas Choy

---

这个程序没有按预期工作。期望的输出是 aaaeiiiou，请注意有三个 i。但对于像 aeiouaaaaaaaaaaaeeeeeeeeeeiiiiiiiiiiioooooouuuuuuuuuu 这样的字符串无法正常工作。 - Tushar

Answer 6

首先，从我对问题的理解来看，输入“aaagtaayuhiejjhgiiiouaae”的结果应该是aaaaaeiiiou，就像@PhamTrung在评论中提出的问题，但没有得到答案。

因为这是一次工作面试，我会从脑海中浮现的第一件事开始，即通过 brute force 来解决这个问题。

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

虽然这个程序的运行时间很糟糕，但我们正在尝试所有可能的只包含元音字母的子字符串，然后丢弃那些不符合要求（a+e+i+o+u+）的字符串，最后选择其中最大的一个。如果我没有错的话，这个算法的最坏情况是∑(n choose i)，即O(n^n) - 好吧，实际上在足够大的n下，最坏情况会导致堆栈溢出异常，这时我们必须使用循环而不是递归来重新实现它。在这种情况下，我们仍然可能遇到内存不足异常，这时我们别无选择，只能改进我们的算法。可以想象，如果输入足够大，我们会遇到内存不足异常，那么我们的代码也会变得足够慢，无法成为解决问题的合理方案。我只是在争论这些问题，因为这些都是面试官可能希望看到你知道的东西，这意味着你了解足够的计算机科学基础知识。

接下来，面试官会问我是否可以改进性能。这是一个具有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()

这可以被看作是 有向无环图上的最长路径问题 的简化版，基本上你会遍历字符串，每个 a 指向下一个 a 和下一个 e 的出现位置。 e 指向下一个 e 和下一个 i 等等。然后你会有一个起始节点指向每个 a 的出现位置，以及一个结束节点由每个 u 的出现位置指向。现在你想要的是从起始节点到结束节点的最长路径，这是一个 O（|V|+|E|）的问题，其中 |V|<=n 且 |E|<=2n，因为你的图中每个节点最多有两个出边，所以总运行时间是 O(n)。我已经简化了代码来构建结果，基本上我已经在构建图时计算了成本，所以当我完成类似于我描述的图的构建时，我已经知道结果是什么。

请注意，此解决方案基于假设输入字符串必然嵌入了一个解决方案。如果输入字符串是无法解决的（其中没有aeiou序列），那么需要正确处理这种情况，实际上很容易添加处理该情况的代码。第一种解决方案将在这种情况下返回null（如果我没有弄错的话）。

希望能对你有所帮助。

- sudavid4

Answer 7

如果你想要找到一个包含最大数量元音字母的子字符串，同时也想要指定子字符串的长度，那么你可以使用这个程序：

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

子字符串的大小越大，具有相同元音数量的子字符串的可能性就越小。

- AWAIS ZAHID

---

aaagtaayuhiejjhgiiiouaae 的输出将是什么？ - AcK

@ack 这取决于你想要的子字符串长度。如果你输入长度为3，那么输出将是： { a,a,a } { i,i,i } { i,i,o } { i,o,u } { o,u,a } { u,a,a } { a,a,e }如果你输入长度为5，那么输出将是： { i,i,i,o,u } { i,i,o,u,a } { i,o,u,a,a } { o,u,a,a,e } - AWAIS ZAHID

我认为你的代码并没有回答这个问题。任务是找到最长的一串“a”，接着是最长的一串“e”，以此类推。 - AcK

@ack实际上确实可以，但它会给您一个额外的选项（子字符串长度）。我在一次工作代码测试中得到了这个问题，所以我分享了它，如果您想要根据问题获得相同的答案，则从函数末尾更改代码即可。 - AWAIS ZAHID