前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

主要就改Code部分~還有紀錄一下C++的一些用法。

Question

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Think

給一個字串s與一個k值，k代表總共有幾個字元可以被替換掉，而s中只會出現大寫的字母(A-Z)，要回傳s中被替換掉k個字元後，同一個字母重複出現的最長的長度。

• 用兩個index(left, right)，主要是由right移動
• 直到right-left+1-dictionary中出現最多次的字母 > k，也就是需要替換的字母數量超過我們可替換的，我們才移動left~
  • 右移left1格的同時，我們把dictionary中s[left]的數量扣1
• 然後每次比較看看我們的最大值有沒有超過原先的~

在CSDN上看到作者： 负雪明烛做的動圖，覺得很方便理解~

Code

class Solution {
public:
    int characterReplacement(string s, int k) {
        unordered_map<char, int> count;
        
        int left = 0;
        int right = 0;
        
        int result = 0;
        int max_count_value = 0;
        
        while(right < s.length()){
            count[s[right]]++;
            max_count_value = max(max_count_value, count[s[right]]);
                
            if ( (right - left + 1) - max_count_value > k){
                count[s[left]]--;
                left++;
            }
            
            result = max(result, (right - left + 1));
            right++;
        }
        // cout << "Result: " << result << endl;
        return result;
    }
};

Submission

• 主要概念跟寫Python的時候差不多，只是在查C++如何找出hash map中的最大value時，發現好像有點麻煩XD，所以另外用一個max_count_value來記錄目前hash map中的最大值~

今天就到這邊啦~
大家明天見