Official
B - DNA Sequence Editorial by evima
First, let us consider what kinds of strings satisfy the condition.
A
is complementary toT
T
is complementary toA
C
is complementary toG
G
is complementary toC
Thus, it is necessary and sufficient that:
- (the number of
A
) = (the number ofT
) - (the number of
C
) = (the number ofG
)
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: