Readme

3579.Minimum-Steps-to-Convert-String-with-Operations

对于区间的问题，我们会思考用区间型的DP是否可行。我们自然会令dp[i]表示针对前i个元素，变换成功所需要的最少操作次数。接下来就是要考虑最后一个区间的位置起点j。因为本题里字符串的长度只有100，我们可以考虑遍历起点j。这样问题就转化为对于区间[j:i]，变化成功所需要的最少操作次数，这样就有dp[i]=dp[j-1]+helper(j,i).

注意到题意中的翻转操作最多只需要一次，我们可以将问题分解成两遍：将word1[j:i]变成Word[j:i]所需要的最少操作数；再将前者翻转一下，同样求变成Word[j:i]所需要的最少操作数。

接下来我们就是设计这样的一个函数，将字符串A怎样高效地只通过swap和replace变成B。贪心是行得通的，因为同一个字符只能用swap或者replace，显然优先使用swap，这样一次操作解决两个地方；等能用的swap都用完了，自然用replace就可以解决剩余的问题。我们用count[a][b]现统计对于字符串A里，字符a需要变成字符b的个数。然后用两个26的循环，遍历所有所有的字符配对{x,y}。显然count[x][y]和count[y][x]可以尽可能地互相抵消，能抵消的就算是swap的操作，剩余不能抵消的部分就是需要的replace的操作。