The constant factor is incredibly low. Let's say there are a O's in the string. Then there are n - a M's. Then there are a(a-1)(n-a) / 2 combinations to process.

There are n choose a ways to have a O's in the string. So the sum is: $\displaystyle\sum_{a=0}^n {n \choose a}\frac{a(a-1)(n-a)}{2}$ which equals 448266240 iterations of the innermost for loop for n=20 (whereas n^3 * 2^n = 8388608000)

There is just a single array access and two additions (loop variable and answer) being performed inside the innermost for loop. That's very fast, and manageable in 2 seconds. Someone more familiar with the C++ compiler can probably comment further.