当前位置: 面试刷题>> 替换后的最长重复字符 (经典算法题500道)


题目描述补充

给定一个字符串 s,你可以进行至多 k 次字符替换操作,使得字符串中某个字符的连续出现次数最大化。返回替换后的最长重复字符子串的长度。

示例 1:

输入:

s = "ABAB", k = 2

输出:

4

解释: 将两个'A'替换为两个'B', 字符串变为 "BBBB",此时最长重复字符子串是 "BBBB",长度为 4。

示例 2:

输入:

s = "AABABBA", k = 1

输出:

4

解释: 将中间的1个'A'替换为'B', 字符串变为 "AABBBBA",此时最长重复字符子串是 "BBBB",长度为 4。

PHP 示例代码

function characterReplacement($s, $k) {
    $maxLen = 0; // 最长重复字符子串的长度
    $maxLengthOfChar = 0; // 当前考虑的字符的最长连续长度
    $left = 0; // 滑动窗口的左边界
    $charCount = array_fill(0, 26, 0); // 存储每个字符的出现次数

    for ($right = 0; $right < strlen($s); $right++) {
        // 更新当前字符的计数
        $charCount[ord($s[$right]) - ord('A')]++;

        // 更新当前考虑的字符的最长连续长度
        $maxLengthOfChar = max($maxLengthOfChar, $charCount[ord($s[$right]) - ord('A')]);

        // 如果窗口内需要替换的字符数超过了k,移动左边界
        if ($right - $left + 1 - $maxLengthOfChar > $k) {
            $charCount[ord($s[$left]) - ord('A')]--;
            $left++;
        }

        // 更新最长重复字符子串的长度
        $maxLen = max($maxLen, $right - $left + 1);
    }

    return $maxLen;
}

// 测试示例
echo characterReplacement("ABAB", 2); // 输出 4
echo "\n";
echo characterReplacement("AABABBA", 1); // 输出 4

Python 示例代码

def characterReplacement(s, k):
    maxLen = 0
    maxLengthOfChar = 0
    left = 0
    charCount = [0] * 26

    for right in range(len(s)):
        charCount[ord(s[right]) - ord('A')] += 1
        maxLengthOfChar = max(maxLengthOfChar, charCount[ord(s[right]) - ord('A')])

        if right - left + 1 - maxLengthOfChar > k:
            charCount[ord(s[left]) - ord('A')] -= 1
            left += 1

        maxLen = max(maxLen, right - left + 1)

    return maxLen

# 测试示例
print(characterReplacement("ABAB", 2)) # 输出 4
print(characterReplacement("AABABBA", 1)) # 输出 4

JavaScript 示例代码

function characterReplacement(s, k) {
    let maxLen = 0;
    let maxLengthOfChar = 0;
    let left = 0;
    let charCount = new Array(26).fill(0);

    for (let right = 0; right < s.length; right++) {
        const index = s.charCodeAt(right) - 'A'.charCodeAt(0);
        charCount[index]++;
        maxLengthOfChar = Math.max(maxLengthOfChar, charCount[index]);

        if (right - left + 1 - maxLengthOfChar > k) {
            charCount[s.charCodeAt(left) - 'A'.charCodeAt(0)]--;
            left++;
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

// 测试示例
console.log(characterReplacement("ABAB", 2)); // 输出 4
console.log(characterReplacement("AABABBA", 1)); // 输出 4

码小课网站中有更多关于算法和数据结构的内容分享,大家可以前往学习更多相关知识。

推荐面试题