LeetCode Biweekly Contest 3 2問目 - Find K-Length Substrings With No Repeated Characters [1100]

Source

LeetCode Biweekly Contest 3
問題文

問題概要

省略

解法

省略

cLay（version 20190630-1）のコード [C++に変換後]

#include<bits/stdc++.h>
using namespace std;
struct Solution{
  public:
  int numKLenSubstrNoRepeats(string S, int K){
    int N=S.size(), arr[26]={}, cnt, i, j, res=0;
    for(i=0;i<N;i++){
      S[i] -= 'a';
    }
    if(N >= K){
      for(i=0;i<K;i++){
        arr[S[i]]++;
      }
      cnt = 0;
      for(j=0;j<26;j++){
        if(arr[j] > 1){
          cnt++;
        }
      }
      for(i=K;;i++){
        if(cnt==0){
          res++;
        }
        if(i==S.size()){
          break;
        }
        if( (--arr[S[i-K]]) == 1 ){
          cnt--;
        }
        if( (++arr[S[i]]) == 2 ){
          cnt++;
        }
      }
    }
    return res;
  }
}
;
// cLay varsion 20190630-1

// --- original code ---
// struct Solution {
// public:
//   int numKLenSubstrNoRepeats(string S, int K) {
//     int i, j, arr[26] = {}, cnt;
//     int N = S.size();
//     int res = 0;
// 
//     rep(i,N) S[i] -= 'a';
// 
//     if(N >= K){
//       rep(i,K) arr[S[i]]++;
// 
//       cnt = 0;
//       rep(j,26) if(arr[j] > 1) cnt++;
//       
//       for(i=K;;i++){
//         if(cnt==0) res++;
//         if(i==S.size()) break;
//         
//         if( (--arr[S[i-K]]) == 1 ) cnt--;
//         if( (++arr[S[i]]) == 2 ) cnt++;
//       }
//     }
// 
//     return res;
//   }
// };
// {
//   // main関数を適当に処理する
// }

Current time: 2024年04月23日22時45分20秒
Last modified: 2019年06月30日03時04分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)