We will describe an approach that solves this problem in at most $$$3*n+3$$$ queries. The first 3 queries are for getting the counts of A,T,G,C.

We can search for 2 characters at once:

Assume that the queried string is "yyyyyyyy...yyyyxyyyyyyy...yy" (x and y are 2 different characters)

If the similarity count has increased by 1 from "yyyyyyyyyyyyyyyy...y" then the character is x, else it is y.

We search for the first 2 characters with the most count, which will take $$$2*n$$$ queries.

Then we search for the last 2 characters, which will take $$$n$$$ queries at most (since at least $$$n$$$ characters have been searched in the string before).

Code: https://mirror.codeforces.com/contest/1981/submission/263736407