How to efficiently calculate prefix sum of frequencies of characters in a string? : <p>Say, I have a string</p>

<pre><code>s = 'AAABBBCAB'
</code></pre>

<p>How can I efficiently calculate the prefix sum of frequencies of each character in the string, i.e.:</p>

<pre><code>psum = [{'A': 1}, {'A': 2}, {'A': 3}, {'A': 3, 'B': 1}, {'A': 3, 'B': 2}, {'A': 3, 'B': 3}, {'A': 3, 'B': 3, 'C': 1}, {'A': 4, 'B': 3, 'C': 1}, {'A': 4, 'B': 4, 'C': 1}]
</code></pre>
