leetcode 424题

leetcode 424 替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

示例1

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例2

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

提示：

1 <= s.length <= 105 s 仅由大写英文字母组成 0 <= k <= s.length**

思路

使用滑动窗口，首先知道的是，需要替换后最长重复字符，一定出现在这个字符串中出现频率最高的字符里面，窗口滑动过程中，用窗口的长度去减去出现频率最大的长度，如果差值比 K 大，那么就要缩小左窗口的值，知道等于 K。res 就不断取出窗口的长度的最大值即可。

代码

var characterReplacement = function(s, k) {
    let left = 0;
    let res = 0;
    let counter = 0;
    let frequence = new Array(26).fill(0);

    for (let right = 0; right < s.length; right++) {
        const distance = s[right].charCodeAt() - 'A'.charCodeAt();
        frequence[distance] += 1;
        counter = Math.max(counter, frequence[distance]);

        while (right - left + 1 - counter > k) {
            frequence[s[left].charCodeAt() - 'A'.charCodeAt()] -= 1;
            left++;
        }

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

    return res;
};

复杂度分析:

时间复杂度: O(N * distance)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 424 替换后的最长重复字符

思路

代码

CATALOG

FEATURED TAGS

FRIENDS