Readme

2712.Minimum-Cost-to-Make-All-Characters-Equal

解法1

我们考察每一处s[i-1]!=s[i]的交界点，为了使他们相等个，我们必须在此处做一次翻转，要么将左边子串全部翻转，要么将右边子串全部翻转，否则无法使得元素相等。

那么选择哪一边翻转呢？从贪心的角度来说，会选择较短的一边翻转。但是这样的贪心会带来什么影响呢？其实没有，选择任何一边进行翻转，都不会改变其他交界点依然需要翻转的事实，以及翻转的策略（即要么将左边子串全部翻转，要么将右边子串全部翻转）。既然如此，索性贪心的策略就是最佳的。

解法2

直观上肯定有一个分界点i，使得[0:i]的翻转一定都是选择左半边，[i+1:n-1]的翻转一定都是选择右半边。我们预处理得到left[i]表示将前缀i依靠左半边翻转都处理成0的最小代价，right[i]表示将后缀i依靠右半边翻转都处理成0的最小代价，然后找到全局最小的left[i]+right[i+1]即可。