I think your idea is workable, though there is still some work to be
done to take care of detail.

But first, you have to know what is the value of $n$ for your input.
And you do not know, and have no simple way to know. So you use the
great trick of automata theory: you guess. You guess by using
non-determinism. The first thing the automaton does is to enter a
state where it write a sting of symbols $a$ on the tape. The state has non
deterministic transitions so that it switches to a new state at some
point, after writing  some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols
$O$.

You must keep carefully your string $a^n$ since it is your reference
number for the computation. But you can use the TM to make as many
copies as needed, using different symbols to avoid
confusion. Basically, you will need one copy $b^n$ to implement a loop counter that
erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you
think hard.

And this is already help beyond a simple hint.

But as stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to guess (and check) ... and that makes life so much easier in automata theory.