Contest Duration: - (local time) (120 minutes) Back to Home

## B - DNA Sequence Editorial by evima

First, let us consider what kinds of strings satisfy the condition.

• A is complementary to T
• T is complementary to A
• C is complementary to G
• G is complementary to C

Thus, it is necessary and sufficient that:

• (the number of A) = (the number of T)
• (the number of C) = (the number of G)

To check if each segment satisfies these conditions, we can, for example, process the segments with the same left end together to solve the problem in a total of $$\mathrm{O}(N^2)$$ time.

Bonus: $$N \leq 2 \times 10^5$$

#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
string S;
cin >> N >> S;
int ans = 0;
for (int i = 0; i < N; ++i) {
int c1 = 0, c2 = 0;
for (int j = i; j < N; ++j) {
if (S[j] == 'A')
c1++;
else if (S[j] == 'T')
c1--;
else if (S[j] == 'C')
c2++;
else
c2--;
if (c1 == 0 && c2 == 0) ans++;
}
}
cout << ans << endl;
return 0;
}


posted:
last update: