问题描述
小R得到了一个由大写字母组成的字符串，长度为 n。她可以对字符串中的字符进行修改，每次操作允许将某个位置的字符修改为任意字符。例如，字符串 ABC 的第一个字符 A 改为 B，则字符串变为 BBC。她最多可以进行 k 次这样的修改。
小R想知道，通过最多 k 次修改后，字符串中由最多两种不同字母组成的最长连续子串的长度是多少。
测试样例
样例1：
输入：
n = 6 ,k = 1 ,inp = "ABCBAD"
输出：5
样例2：
输入：
n = 5 ,k = 1 ,inp = "AEABD"
输出：4
样例3：
输入：
n = 8 ,k = 2 ,inp = "AAAABBCD"
输出：8
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>using namespace std;int solution(int n, int k, std::string s) {if (n <= 2)return n;int max_len = 0;unordered_set<char> char_set(s.begin(), s.end());vector<char> chars;for (auto &p : char_set)chars.push_back(p);for (char char1 : chars) {for (char char2 : chars) {if (char1 == char2)continue;int left = 0;int count1 = 0;int count2 = 0;int total = 0;for (int right = 0; right < n; ++right) {total++;if (s[right] == char1)count1++;else if (s[right] == char2)count2++;while (total - count1 - count2 > k) {if (s[left] == char1)count1--;else if (s[left] == char2)count2--;left++;total--;}max_len = max(max_len, total);}}}for (char char1 : chars) {int left = 0;int count = 0;int total = 0;for (int right = 0; right < n; ++right) {total++;if (s[right] == char1)count++;while (total - count > k) {if (s[left] == char1)count--;++left;--total;}max_len = max(max_len, total);}}return max_len;
}int main() {std::cout << (solution(6, 1, "ABCBAD") == 5)<< std::endl; // Expected: 1 (true)std::cout << (solution(5, 1, "AEABD") == 4)<< std::endl; // Expected: 1 (true)std::cout << (solution(8, 2, "AAAABBCD") == 8)<< std::endl; // Expected: 1 (true)return 0;
}package mainimport ("fmt"
)// solution 返回通过最多 k 次修改后，包含最多两种字母的最长子串长度
func solution(n, k int, s string) int {if n <= 2 {return n}maxLen := 0// 获取唯一字符集合charSet := make(map[rune]bool)for _, c := range s {charSet[c] = true}// 将字符放入切片chars := make([]rune, 0, len(charSet))for c := range charSet {chars = append(chars, c)}// 枚举两种字母组合for _, char1 := range chars {for _, char2 := range chars {if char1 == char2 {continue}left, count1, count2, total := 0, 0, 0, 0for right := 0; right < n; right++ {total++if rune(s[right]) == char1 {count1++} else if rune(s[right]) == char2 {count2++}// 缩小窗口直到修改次数 <= kfor total-count1-count2 > k {if rune(s[left]) == char1 {count1--} else if rune(s[left]) == char2 {count2--}left++total--}if total > maxLen {maxLen = total}}}}// 处理单一字母的情况for _, char1 := range chars {left, count, total := 0, 0, 0for right := 0; right < n; right++ {total++if rune(s[right]) == char1 {count++}for total-count > k {if rune(s[left]) == char1 {count--}left++total--}if total > maxLen {maxLen = total}}}return maxLen
}func main() {testCases := []struct {n intk ints string}{{6, 1, "ABCBAD"},{5, 1, "AEABD"},{8, 2, "AAAABBCD"},}for _, tc := range testCases {fmt.Println(solution(tc.n, tc.k, tc.s))}
}def solution(n, k, s):if n <= 2:return nmax_len = 0# 获取唯一字符集合chars = set(s)# 枚举两种字母组合for char1 in chars:for char2 in chars:if char1 == char2:continueleft = 0count1 = 0 # char1 的数量count2 = 0 # char2 的数量total = 0 # 窗口总长度for right in range(n):total += 1if s[right] == char1:count1 += 1elif s[right] == char2:count2 += 1# 缩小窗口直到修改次数 <= kwhile total - count1 - count2 > k:if s[left] == char1:count1 -= 1elif s[left] == char2:count2 -= 1left += 1total -= 1max_len = max(max_len, total)# 处理单一字母的情况for char1 in chars:left = 0count = 0total = 0for right in range(n):total += 1if s[right] == char1:count += 1while total - count > k:if s[left] == char1:count -= 1left += 1total -= 1max_len = max(max_len, total)return max_len# 测试代码
if __name__ == "__main__":test_cases = [(6, 1, "ABCBAD"),(5, 1, "AEABD"),(8, 2, "AAAABBCD"),]for n, k, s in test_cases:print(solution(n, k, s))
