シミュレートをすることによっても答えは求まりますが、最も左の "MM" から最も右の "A" までは長さが になるまで操作を行えます。 以下にその証明を示します。
右端のみが "A" で、それ以外が "M" である文字列、すなわち "MM...MA"という文字列は、最も右の "MMA" となる文字列を "MA" に置き換え続けることで、最終的に "MA" という文字列が得られます。
次に、 "MM...MMAM...MA" という文字列は間に含まれる "MMA" という文字列を "MM" に置き換えることで、"MM...MMM...MA" という文字列が得られます。
間に "A" が複数存在するときも同様に "MM...MA" という文字列を生成できます。
回の操作では常に 文字ずつ減っていくので、最も左の "MM" から最も右の "A" までの文字列を "MM...MA" の形にした後、"MA" が得られるまで操作をし続けることにより、(その文字列の長さ) - 回だけ操作を行え、これが答えとなります。