If you go through the discussion so far, you will notice that there is a method of judgment. In fact, noticing it is the key to this problem, so if you haven't come to the point, think about it for a while.

………That's right! When the substring $ T $ is rearranged, the $ "A" $ and $ "T" $ contained in ** $ T $ must be present in order to have a string complementary to $ T $. Must be equal in number and $ "C" $ and $ "G" $ must be in equal numbers **.

Now the problem is ** "$ S $ is a contiguous non-empty substring $ T $, and the number of " A " and " T " contained in $ T $ is equal. , And find the number of things with the same number of $ "C" $ and $ "G" $ "**" can be replaced with the problem.

In this way, it is also important for competition professionals to "replace problem sentences with easy-to-understand forms."

Step2: Think of a straightforward solution

Now that the problem has been summarized briefly, let's consider a solution. At this time, the constraint of the value given by the standard input is very helpful. In this case, $ N <= 5000 $, so the $ O (N ^ 2) $ solution will be in time (for those who do not understand the concept of computational complexity order, [this site](https: // bmf-tech) .com / posts / O (order) notation and how to calculate the computational complexity of the algorithm #: ~: text = Computational complexity (order) is an index expressed as a percentage.)).

Now that we know the upper limit of the amount of calculation, let's think about the solution in earnest. Step 1 shows that if you know the number of $ "A", "T", "C", "G" $ in $ T $, you can determine if $ T $ has a complementary string. So, for the time being, I will write it honestly.

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = Array(input[1]).map{String($0)}
var answer = 0
for i in 0..<n-1{
    for j in i+1..<n{
        var ac = 0
        var tc = 0
        var cc = 0
        var gc = 0
        for k in i...j{
            if s[k] == "A"{ac += 1}
            if s[k] == "T"{tc += 1}
            if s[k] == "C"{cc += 1}
            if s[k] == "G"{gc += 1} 
        }
        if ac == tc && cc == gc{answer += 1}
    }
}
print(answer)

If you actually put in a test case, you can see that you are looking for the correct answer. However, the amount of calculation of this program is $ O (N ^ 3) $, which will cause you to get stuck in the execution time limit (When you actually submit it, it looks like this / contests / arc104 / submissions / 17643029))). In this way, if you estimate the upper limit of the amount of calculation first, you can prevent you from taking a penalty by submitting a code that becomes TLE.

Step3: Speed up the program

From here, let's think about how to speed up. In the first place, it costs $ O (N ^ 2) $ to specify a substring, so ** "Determine whether a complementary string exists with $ O (1) $" You have to think of ** or ** "how to solve without specifying individual substrings" **. ~~ This problem seems to work well if you think about the former. If you manage the amount, you will gradually understand "which point should be focused on to speed up", so don't worry if you don't know now. ~~

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = input[1]
var aa:[Int] = [0]
var tt:[Int] = [0]
var cc:[Int] = [0]
var gg:[Int] = [0]
var a = 0
var t = 0
var c = 0
var g = 0
//Preprocessing to use cumulative sum
for i in s{
    if i == "A"{a += 1}
    if i == "T"{t += 1}
    if i == "C"{c += 1}
    if i == "G"{g += 1}
    aa.append(a)
    tt.append(t)
    cc.append(c)
    gg.append(g)
}
//From here on, it's the same as the straightforward method I created earlier
var ans = 0
for i in 0...n-1{
    for j in i+1...n{
        if aa[j]-aa[i] == tt[j]-tt[i] && cc[j]-cc[i] == gg[j]-gg[i]{
            ans += 1
        }
    }
}
print(ans)

Specifically, I would like to explain how to solve the latter case. First, let's see how the program written in Step 2 works. Then you will notice that the calculation is wasteful. Specifically, it is the ↓ part.

for j in i+1..<n{
    //Abbreviation
    for k in i...j{
        //Abbreviation
    }

If you follow the flow of the program moving carefully one by one,

Find the value of $ i ... j $ in a loop Find the value of $ → i ... j + 1 $ in a loop Find the value of $ → i ... j + 2 $ in a loop Repeat below $ → $

You can see that it works like this. However, if you think about it, the value of $ i ... j + 1 $ can be obtained by simply adding the value of $ j + 1 $ to the value of $ i ... j $. It is a wasteful calculation to recalculate the value of $ i ... j $. Similarly, when finding the value of $ i ... j + 2 $, simply add the value of $ j + 2 $ to the value of $ i ... j + 1 $.

So what I mean is that ** a value once calculated can be used to find the next value **. If this is improved, the amount of calculation can be reduced to $ O (N ^ 2) $ without using the cumulative sum. When implemented, it will be as follows.

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = Array(input[1]).map{String($0)}
var answer = 0
for i in 0..<n-1{
    var ac = 0
    var tc = 0
    var cc = 0
    var gc = 0
    for j in i..<n{
        if s[j] == "A"{ac += 1}
        if s[j] == "T"{tc += 1}
        if s[j] == "C"{cc += 1}
        if s[j] == "G"{gc += 1} 
        if ac == tc && cc == gc{answer += 1}
    }
}
print(answer)

If you try to extract the part that has been used for unnecessary calculations in this way, it will be a story that "That's right", but it is hard to notice unless you are accustomed to it. At the beginning, it is recommended to solve it with the feeling of "thinking about a straightforward solution" → "looking at the flow of the program and looking for unnecessary calculations".

Finally

This is the end of the explanation. The explanation may have been difficult to understand in many places (I'm not strong enough, I'm sorry), but I hope it conveys the general atmosphere when solving the problem. As I wrote at the beginning, if you have any questions, please feel free to comment or Twitter.