Replacements Of A And B

(laicode Class99)

Given a string with only character 'a' and 'b', replace some of the characters such that the string becomes in the forms of all the 'b's are on the right side of all the 'a's.

Determine what is the minimum number of replacements needed.

Assumptions:

• The given string is not null.

Examples:

"abaab", the minimum number of replacements needed is 1 (replace the first 'b' with 'a' so that the string becomes "aaaab").

Analysis

link:

https://piazza.com/class/j0eqhhdregb3i?cid=479

https://piazza.com/class/j0eqhhdregb3i?cid=1859

DP: DP1[len] DP2[len]

从左到右数: 在index = i 的时候, DP1[i] = 如果把0~i全变成'a'需要多少次替换

从右到左数: 在index = i 的时候 DP2[i] = 如果吧i~len-1全变成'b'需要多少次替换.

最后算从0~len-1 , 哪里DP1[i] + DP2[i + 1] 的值最低.