aab aba baa (Hard version)

まず$S$のaを0に，bを1に変換します． すると，$S$は先頭に$0$を許した$(A+B)$桁の$2$進数とみなすことができます．

次に，以下の言い換えが成立します．

• $S$がaが$A$個，bが$B$個からなる文字列のうち辞書順で何番目か $\Rightarrow$ $S$を01文字列に変換して$2$進数として見て，それより小さくて1の数が$B$個である$2$進数の個数$+1$

これは，桁数が同じもの同士の大小関係はそれらを文字列とみなしたときの辞書順の大小関係と一致し， 桁数が足りない場合は$(A+B)$桁になるまで0で埋めればよいことから従います．

よって「$S$を01文字列に変換して$2$進数として見て，それより小さくて1の数が$B$個である$2$進数の個数」を求めればよいです． これは桁DPという方法で求めることができ，その時の時間計算量は$O(|S|^2)$です．