AtCoder Regular Contest 104 B - DNA Sequence

問題について考えたこと

問題文

Aに対してTのある文字列というだけでなく、 もとの文字列を並び替えた文字列ということから AとTが同じ数、CとGが同じ数ならよいのではと考えました。

部分文字列については、０文字目から最後まで１文字ずつずらす、 １文字目から最後まで１文字ずつずらす事しか思いつきませんでした。

制約から、間に合うだろうと考え実装しました。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = (1LL<<62) - (1LL<<31);
const ll MOD = 1000000007;


int main(void) {
  int N;
  cin >> N;
  string S;
  cin >> S;

  ll ans = 0;
  for (int i = 0; i < N - 1; ++i) {
    int A = 0, T = 0, C = 0, G = 0;
    for (int j = i; j < N; ++j) {
      if (S[j] == 'A') ++A;
      else if (S[j] == 'T') ++T;
      else if (S[j] == 'C') ++C;
      else if (S[j] == 'G') ++G;

      if (A == T && C == G) ++ ans;
    }
  }

  cout << ans << endl;
  
  return 0;
}