[LeetCode] 2953. Count Complete Substrings

• 難度分: 2449
• 這題是一個定長的 sliding window，比較難想的是 window size 是 k * 1, k * 2, … 到 k * 26，因為只有 26 個英文字母，所以最多只可能到 26 * k 的長度。
• 額外需要檢查相鄰的字母是否距離 <= 2，我使用的方法是找到一個 j 記錄最大的不符合的索引值，所以直要 window 不包含該 j，window 內的所字元都會滿足。
• 所以 pesudo code 會是

  for (int c = 1; c <= 26; i++) {
      // window size
      int windowSize = c * k;
      // construct window
      for (int i = 0; i < windowSize; i++) {
          // 處理 j
          // 計算進入 window
      }
  
      // 確認初始的 window 是否滿足
  
      // rolling windo
      for (int i = windowSize; i < n; i++) {
          // 處理 j
          // 計算進入 window
          // 計算離開 window
  
          // 確認 window 是否滿足
      }
  }

class Solution {
public:
    int countCompleteSubstrings(string s, int k) {
        int n = s.size();
        int res = 0;
        for (int idx = 1; idx <= 26 && idx * k <= n; idx++) {
            int len = idx * k;
            int j = -1;
            vector<int> cnt(26, 0);
            int valid = 0;
            for (int i = 0; i < len; i++) {
                if (i > 0 && abs(s[i] - s[i-1]) > 2) {
                    j = i-1;
                }
                if (++cnt[s[i]-'a'] == k) valid++;
            }
            if (valid == idx && j < 0) {
                res++;
            }

            for (int i = len; i < n; i++) {
                if (abs(s[i] - s[i-1]) > 2) {
                    j = i-1;
                }
                if (++cnt[s[i]-'a'] == k) valid++;
                if (cnt[s[i-len]-'a']-- == k) valid--;
                if (valid == idx && i-len >= j) {
                    res++;
                }
            }
        }
        return res;
    }
};