LeetCode 75 Level 1 - Day 12 Sliding Window/Two Pointer

424. Longest Repeating Character Replacement

• 題目連結
• 難易度：Medium

題目敘述

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.

預設函數

int characterReplacement(char * s, int k){

}

題目限制

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

解題過程及程式碼

本題給一個字串s及整數k，要求出若將s裡的某一個字母換成任意字母，在最多可以進行k次後，字串s裡最長的連續字元有多長?

• 例如Input: s = "ABAB", k = 2，可以將s裡的A都換成B (這樣換2次)得到"BBBB"，所求為4，也可以將s裡的B都換成A (也是換2次)得到"AAAA"，所求為4。
• 例如Input: s = "AABABBA", k = 1，將index=3的A換成B (換1次)得到"AABBBBA"，最長連續字元為4。

初始想法就是利用滑動視窗(有視窗開頭和視窗長度2個變數)進行檢查，由大到小，從全字串長度n為視窗長度開始檢查會有1種可能，n-1有2種可能，一直到視窗長度為1有n種可能。

某些字母改變後要最長連續的話，只要視窗裡面出現最多次數的字母數量是 (字串長度(n) - 可變換次數(k))，在改變後就可以達到最長連續字串，使用這種檢查方式在字串很大時會超過時間限制 (Time Limit Exceeded)，因為有很多組合是不需要計算的，而且花費很多時間在計算字串的字母數量。

• Time Limit Exceeded程式碼

  int characterReplacement(char * s, int k){
      int i = 0;
      int j = 0;
      int len = strlen(s);
      int break_flag = 0;
  
      for (i=0; i<len; i++) {
          for (j=0; j<(i+1); j++) {
              if (checkLetter(s, j, len - i, k) == 1) {
                  break_flag = 1;
                  break;
              }
          }
          if (break_flag == 1) {
              break;
          }
      }
  
      return (len - i);
  }
  
  int checkLetter(char * s, int start, int len, int input_k) {
      int char_array[26] = {0};
      int max_num = 0;
      int ret = 0;
  
      for (int i=start; i<(start+len); i++) {
          char_array[s[i] - 'A'] += 1;
      }
  
      for (int i=0; i<26; i++) {
          if (char_array[i] >= max_num) {
              max_num = char_array[i];
          }
      }
  
      if (max_num == len) {
          return 1;
      }
  
      for (int i=input_k; i>=0; i--) {
          if ((max_num + i) == len) {
              ret = 1;
              break;
          }
      }
  
      return ret;
  }
  

參考網路上的做法，窗口只會變大或移動，不會縮小，窗口大小就是最終結果 (MAX_COUNTER跟著右邊界更新)

• 【Leetcode】python – [424] Longest Repeating Character Replacement 個人解法筆記 #重要題型
• LeetCode——424. 替換後的最長重複字元(Longest Repeating Character Replacement)——分析及程式碼（Java）
• Leetcode每日一题：424.longest-repeating-character-replacement(替换后的最长重复字符)
• 程式碼上傳

#define MAX(a,b) (((a)>(b))?(a):(b))

int characterReplacement(char * s, int k){
    int i = 0;
    int maxCnt = 0, start = 0, len = strlen(s);
    int char_array[26] = {0};

    for (i = 0; i < len; ++i) {
        char_array[s[i] - 'A'] += 1;
        maxCnt = MAX(maxCnt, char_array[s[i] - 'A']);
        if (i - start + 1 - maxCnt > k) {
            --char_array[s[start] - 'A'];
            ++start;
        }
    }
    return i - start;
}

參考影片

• Longest Repeating Character Replacement - Leetcode 424 - Python - YouTube

今天到這邊，感謝看完。