javascript - 查找字符串中出现时间最长的 "aeiou"

Question

我最近在接受采访，被问了很多问题，其中一个问题就是这个，我在尝试回答时遇到了一些麻烦。

给定一个字符串，找到出现时间最长的元音字母“aeiou”。元音子串不必连续，可以有重复。

目标是找到每个元音的最大出现次数并将它们连接起来，但必须按照“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");

至少我的方向是正确的吗？

提前致谢。

Answer 1

我们可以在 O(n) 中解决这个问题时间。考虑对于每个 block ，如果它的元音位于索引 v 处在元音列表中，我们只对索引为元音的 block 的最佳解决方案感兴趣 v-1 按元音顺序。我们在进行过程中为每种 block 类型(每个元音)保存最后的最佳解决方案:

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