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 <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

解法

方法一：双指针

我们使用一个哈希表 cnt 统计字符串中每个字符出现的次数，使用双指针 l 和 r 维护一个滑动窗口，使得窗口的大小减去出现次数最多的字符的次数，结果不超过 \(k\)。

我们遍历字符串，每次更新窗口的右边界 r，并更新窗口内的字符出现次数，同时更新出现过的字符的最大出现次数 mx。当窗口的大小减去 mx 大于 \(k\) 时，我们需要缩小窗口的左边界 l，同时更新窗口内的字符出现次数，直到窗口的大小减去 mx 不大于 \(k\)。

最后，答案为 \(n - l\)，其中 \(n\) 为字符串的长度。

Python3JavaC++GoTypeScript

class Solution: def characterReplacement(self, s: str, k: int) -> int: cnt = Counter() l = mx = 0 for r, c in enumerate(s): cnt[c] += 1 mx = max(mx, cnt[c]) if r - l + 1 - mx > k: cnt[s[l]] -= 1 l += 1 return len(s) - l 

class Solution {  public int characterReplacement(String s, int k) {  int[] cnt = new int[26];  int l = 0, mx = 0;  int n = s.length();  for (int r = 0; r < n; ++r) {  mx = Math.max(mx, ++cnt[s.charAt(r) - 'A']);  if (r - l + 1 - mx > k) {  --cnt[s.charAt(l++) - 'A'];  }  }  return n - l;  } } 

class Solution { public:  int characterReplacement(string s, int k) {  int cnt[26]{};  int l = 0, mx = 0;  int n = s.length();  for (int r = 0; r < n; ++r) {  mx = max(mx, ++cnt[s[r] - 'A']);  if (r - l + 1 - mx > k) {  --cnt[s[l++] - 'A'];  }  }  return n - l;  } }; 

func characterReplacement(s string, k int) int {  cnt := [26]int{}  l, mx := 0, 0  for r, c := range s {  cnt[c-'A']++  mx = max(mx, cnt[c-'A'])  if r-l+1-mx > k {  cnt[s[l]-'A']--  l++  }  }  return len(s) - l } 

function characterReplacement(s: string, k: number): number {  const idx = (c: string) => c.charCodeAt(0) - 65;  const cnt: number[] = Array(26).fill(0);  const n = s.length;  let [l, mx] = [0, 0];  for (let r = 0; r < n; ++r) {  mx = Math.max(mx, ++cnt[idx(s[r])]);  if (r - l + 1 - mx > k) {  --cnt[idx(s[l++])];  }  }  return n - l; } 

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

题目描述

解法

方法一：双指针

评论