Difficulty: Medium
Link: https://leetcode.com/problems/longest-repeating-character-replacement/
Problem
Explanation
- 這道題目我自己沒有想到解法磁滚，是看了LeetCode上的討論之后明白的铺韧。中心思想就是滑動窗口吕粹，通過往
s[i:j]窗口中不斷添加新的字符悯嗓，如果符合條件則繼續(xù)添加（擴大窗口的大型箍恕）寝志，而不符合條件的話吗讶，則將窗口的起始位置i + 1瑞眼，即將窗口右滑躺率。最終求的結(jié)果是連續(xù)的相同字符子串的長度玛界，所以就如同是一個不斷開的連續(xù)窗口。 - 之前我陷入的誤區(qū)悼吱，是如何替換字母慎框，其實根本不應(yīng)該去考慮去替換字符串，應(yīng)該考慮最終的結(jié)果后添。因為最終的結(jié)果必定是子串
s[i:j], i >= 0, j < s.size()笨枯，從結(jié)果考慮的話，最終符合的條件就是j - i - *max_element(alp + 65, alp + 91) <= k
*max_element(alp + 65, alp + 91)就是在s[i:j]范圍內(nèi)遇西，字母A-Z中數(shù)量最大的字符的數(shù)量馅精，例如"AAABCC"，結(jié)果就是3粱檀。取這個值的原因是：這樣可以通過替換最少的字母而達到最長的重復(fù)字符子串)
cpp solution
class Solution {
public:
int characterReplacement(string s, int k) {
int i = 0, j = 0, alp[91] = {};
while (j < s.length()) {
alp[s[j++]]++;
if ((j - i - *max_element(alp + 65, alp + 91)) > k) {
alp[s[i++]]--;
}
}
return j - i;
}
};
