6455. 使所有字符相等的最小成本 (opens new window)

1.贪心

解题思路：从前往后遍历数组，保证从0到i字符串中所有字符都是相同。遇到当前字符和下一个字符不同的情况有两种操作，选用其中成本小的反转方式。

• 从前面反转，翻转从0到第i字符，使第i个字符和i+1个字符保持一致
• 从后面反转，翻转第i+1个字符到最后一个字符。

何为贪心，解题核心如下：

• 对于任意相邻的两个字符，能够操作的方式一共就只有两种，一种要么翻转前面的字符串，另一种是翻转后半部分字符串。
• 翻转操作是翻转当前位置到字符串头元素或者到尾元素，因此只要两个相邻字符是相同的，那么后续无论翻转多少次它们都能保证是相同。因此可以把问题聚焦于让两个相邻的字符相同的最小操作数上这个子问题。
• 翻转时，不需要固定到底是保证所有字符串都是1还是0。

class Solution {
    public long minimumCost(String s) {
        long ans=0;
        for(int i=0;i+1<s.length();i++){
            if(s.charAt(i)!=s.charAt(i+1)){
                ans+=(i+1>s.length()-i-1)?s.length()-i-1:i+1;
            }
        }
        return ans;
    }
}