替換后的最長重復字符
給你一個僅由大寫英文字母組成的字串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次，在執行上述操作后，找到包含重復字母的最長子串的長度，
注意：字串長度 和 k 不會超過 10^4，
示例 1：
輸入：s = “ABAB”, k = 2
輸出：4
解釋：用兩個’A’替換為兩個’B’,反之亦然，
示例 2：
輸入：s = “AABABBA”, k = 1
輸出：4
解釋：
將中間的一個’A’替換為’B’,字串變為 “AABBBBA”，子串 “BBBB” 有最長重復字母, 答案為 4，
解題思路
首先，遍歷字串 s，得到每個元素在字母表中的位置(A 對應位置 0，B 對應位置 1，以此類推)來代替字串中的每個字符，并且，記錄當前視窗中每個元素出現的次數，得到視窗內相同元素的最大個數，
若當前視窗中相同元素的最大個數與替換次數 k 之和 < 當前視窗大小(則說明此時不能完全替換掉不同的字母，得到相同字母的子串)，此時應該使 left 指標右移縮小視窗，
代碼
class Solution {
public int characterReplacement(String s, int k) {
int maxsame = 0;//存盤的是視窗內相同元素的最大個數
int n = s.length();
int[] arr = new int[26];//arr中存放的當前視窗中每個元素出現的次數
int left = 0, right;
for (right=0;right<n;++right) {
//得出索引，ASCLL碼----A對應位置0，B對應位置1，以此類推...
int index = s.charAt(right) - 'A';
//數目加1，因為我們要求出視窗內最多元素
arr[index]++;
//得出最大maxsume(視窗內相同的元素個數)
maxsame = Math.max(maxsame, arr[index]);
//當前視窗中相同元素的最大個數與替換次數之和 < 當前視窗大小
//(則說明此時不能完全替換掉不同的字母，得到相同字母的子串，)----縮小視窗
if (maxsame + k < right - left + 1) {
arr[s.charAt(left) - 'A']--;
left++;
}
}
return right - left;
}
}
時間復雜度：因為只遍歷了一次字串，且字串的長度為 n，所以復雜度為O(n)
空間復雜度：因為開辟了新的空間，所以復雜度為O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/260274.html
標籤：其他
上一篇：vue SEO的解決方案