<p>The cost does not depend on the order of characters. If a character <code>c</code> appears <code>x</code> times, the cost is exactly <code>0 + 1 + 2 + … + (x − 1) = x * (x − 1) / 2</code>.</p>

<p>We know the total number of question marks; for each one, we should select the letter with the minimum frequency to replace it.</p>

<p>The letter selection can be achieved by a min-heap (or even by brute-forcing the <code>26</code> possibilities).</p>

<p>So, we know the extra letters we need to replace finally. However, we must put those letters in order from left to right so that the resulting string is the lexicographically smallest one.</p>