JS拼接单词数组求解最长单字符重复子串问题求助

现有代码问题汇总 #

• 未定义longestSubstring函数，调用时返回undefined，直接拼接进字符串就会出现你遇到的undefined字符
• 剩余元素计算错误：arr.slice(0,i) + arr.slice(i + 1)是将两个数组合并成字符串，而非得到剩余元素的数组，导致后续遍历逻辑完全错误
• 全排列逻辑缺失：没有正确的递归终止条件，无法生成所有可能的数组排列
• 最长连续子串计算逻辑错误：三重循环逻辑混乱，cur_count没有每次重置，计算出的长度完全不符合预期
• 返回值格式错误：需求要求返回包含letter和length属性的对象，现有代码返回的是拼接字符串

正确实现代码 #

function longestSingleCharSubstring(arr) {
    // 生成数组的所有全排列
    function permute(words) {
        if (words.length === 1) return [words];
        const res = [];
        for (let i = 0; i < words.length; i++) {
            const current = words[i];
            const rest = words.slice(0, i).concat(words.slice(i + 1));
            const restPermute = permute(rest);
            for (let p of restPermute) {
                res.push([current, ...p]);
            }
        }
        return res;
    }

    // 计算单个字符串的最长连续单字符信息
    function getMaxLongest(str) {
        let maxLen = 1;
        let curLen = 1;
        let maxLetter = str[0];
        for (let i = 1; i < str.length; i++) {
            if (str[i] === str[i-1]) {
                curLen++;
                if (curLen > maxLen) {
                    maxLen = curLen;
                    maxLetter = str[i];
                }
            } else {
                curLen = 1;
            }
        }
        return { letter: maxLetter, length: maxLen };
    }

    const allPermutes = permute(arr);
    let globalMax = { letter: '', length: 0 };
    for (let p of allPermutes) {
        const combinedStr = p.join('');
        const currentMax = getMaxLongest(combinedStr);
        if (currentMax.length > globalMax.length) {
            globalMax = currentMax;
        }
    }
    return globalMax;
}

// 测试示例
console.log(longestSingleCharSubstring(["ccdd", "bbbb", "bbab"])); // 输出 { letter: 'b', length: 6 }

优化说明 #

如果数组长度超过10，全排列的时间复杂度O(n!)会非常高，实际场景下可以不用全排列，只需要统计每个字符的前后缀连续长度、全字符单词长度，直接计算最大可能的连续长度，时间复杂度可以降到O(n*m)，n是单词数，m是单词平均长度。

内容的提问来源于stack exchange，提问作者user16722579