如何查找由相同字符组成的最长子字符串？

Question

现在我试着解决查找长度最长的子字符串由相同的字符组成的任务。例如，我有一个字符串yyuuufhvksoooo，那么我将得到结果4。

我写了这个代码，那就是：

function longRepeat(line) { 
    if (line.length > 0) { 
    var count = 1; 
    var max = 1; 
    } 
    for (let i = 0; i < line.length - 1; i++) { 
    if (line[i] == line[i + 1]) { 
     count++; 
     if (count > max) max = count; 
    } else { 
     count = 1; 
    } 
    } 
    return max; 
} 

这就是工作。但是当我用大字符串测试这个代码时，我发现这个任务的框架，给我错误You process has been killed because of using too much resources。 如何更有效地执行我的代码？

Answer 1

您可以使用第二个变量j的嵌套循环从当前的i位置向前移动，直到找到不匹配的字符。那么如果j和i之间的差值大于最大值，则将其分配为最大值。

每次迭代后，i的下一个值变为j的值，因为它已经完成了向前移动至少一个位置的工作。

function longRepeat(line) { 
 
    if (!line.length) { 
 
    return 0 
 
    } 
 
    var max = 1; 
 
    for (let i = 0, j = 0; i < line.length - 1; i = j) { 
 
    for (j = i + 1; j < line.length && line[j] == line[i]; j++) { 
 
     // No more work to do here 
 
    } 
 

 
    if (j - i > max) { 
 
     max = j - i; 
 
    } 
 
    } 
 
    return max; 
 
} 
 

 
console.log(longRepeat("yyuuufhvksoooo"));

---

你指的是在讨论的问题还不清楚。您可以尝试批量处理，但很难确切地知道解决方案对于该问题没有更多信息。

---

下面是执行较少的指定和比较，这可能是一个小更高效的版本。

function longRepeat(line) { 
 
    if (!line.length) { 
 
    return 0 
 
    } 
 

 
    let max = 1; 
 
    let i = 0; 
 
    while (i < line.length-1) { 
 
    const j = i; 
 
    while (line[++i] == line[j]) { 
 
     // No more work to do here 
 
    } 
 

 
    if (i - j > max) { 
 
     max = i - j; 
 
    } 
 
    } 
 
    return max; 
 
} 
 

 
console.log(longRepeat("yyuuufhvksoooo"));

Answer 2

写有内置的JavaScript功能函数

• 正则表达式匹配相同的字符&分裂的子字符串匹配到一个数组
• 地图数组，并获得每个字的长度
• 查找字长度的最大值

var findMaxLength = function(inputString){ 
 
\t \t var arrChuncks = inputString.match(/(.)\1*/g); 
 
\t \t var arrChunkLengths = arrChuncks.map(function(i){return i.length}) 
 
\t \t return Math.max.apply(null, arrChunkLengths) 
 
} 
 

 
var testString = "turpis venenatis porta. Maecenas et ultricies dui, ut accumsan metus. Duis ut odio at risus tincidunt scelerisque. Duis placerat efficitur posuere. Nam sit amet tincidunt purus. Maecenas urna nibh, imperdiet quis dui nec, congue maximus nisl. Vestibulum a magna pellentesque, ultricies libero id, porta lorem.Morbi eu ex mi. In pulvinar sit amet libero felis.Pellentesque tellus dui, blandit vitae felis sed, rutrum volutpat tortor. Morbi consequat finibus leo quis porta. Aliquam varius ipsum in lorem varius mollis. Vivamus id ultricies tortor, sed rhoncus nisi. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuerebbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cubilia Curae; Class aptent taciti sociosqu ad litora torquent per conubia nostra, ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccper inceptos himenaeos. Sed et massa in metus elementum sodales. Vestibulum id metus risus. Aliquam consequat at ante ut lobortis.Etiam vitae arcu et nisi laoreet gravida id id magna. Sed rutrum lacus ut enim vulputate facilisis. e platea dictumst. Donec rhoncus, ex at commodo volutpat, augue nulla rhoncus quam, ut pulvinar mi neque consectetur risus. Morbi tempor rhoncus mauris, sit amet tincidunt libero ultrices iaculis. Nulla erat dui, llis turpis non eros varius, mollis dictum neque vehicula. Aenean est felis, pellentesque non lectus vel, ultricies venenatis dui. Vivamus dictum lorem cursus hendrerit molestie. Aenean ornare malesuada fames ac turpis egestas. Aliquam id bibendum turpis. Morbi in imperdiet elit.Sed in rhoncus purus. Nullam consequat nulla magna, in porttitor enim auctor feugiat. Nunc blandit, orci non vehicula malesuada, elit velit varius odio, id lobortis lectus purus in dui. Quisque massa nulla, convallis a mi vel, sagittis tincidunt lacus. "; 
 

 
document.getElementById('output').innerHTML = findMaxLength(testString);

Max Length : 
 
<div id='output'></div>

Answer 3

我知道你已经接受一个答案，但也许仍有改进的空间对于一个很大的字符串，其中平均，你可以期望有相同的字符范围变得更长。

这个想法是，当你已经有一个相同字符序列的最大长度是10时，只要你在那里找到的字符与前一个字符不同，就可以前进5步。你可以这样做，因为当你知道每次跳跃5的字符不同时，无法适应11个相同字符的序列。

在随机的长输入字符串中，这可能意味着您将能够以这种方式跳过很多字符。

当然，当这样的测试显示角色相同时，您仍然必须返回并检查序列的真实时间。但这仅仅意味着你将会访问你在已接受的算法中访问过的角色。所以那里几乎没有损失。成本是在额外的“跳跃”测试。在最坏的情况下，你会在每次跳跃5时发现相同的字符，并且仍然发现不再有相同字符的序列。但随机输入，每个位置（或更多）有26个可能的字符，它们更有可能是不同的，并且可以跳过很多。

下面是代码：

function longRepeat(line) { 
 
    if (!line.length) { 
 
    return 0; 
 
    } 
 
    var max = 1, jump = 1, i, j, k, prev; 
 
    for (i = 0, j = 0; i < line.length - 1; i = j) { 
 
    prev = line[i]; 
 
    j = i + jump; 
 
    if (line[j] !== prev) continue; // quick jump 
 
    for (j = i + 1; j < line.length && line[j] === prev; j++) { 
 
     // No more work to do here 
 
    } 
 
    for (k = i - 1; line[k] === prev; k--) { 
 
     // Looking backwards: no work either 
 
    } 
 
    if (j - k - 1 > max) { 
 
     max = j - k - 1; 
 
     jump = (max+1) >> 1; 
 
    } 
 
    } 
 
    return max; 
 
} 
 

 
console.log(longRepeat("yyuuufhvksoooo"));