LeetCode #1864 构成交替字符串需要的最小交换次数_动态规划字符串中使相邻字符不相等的最少替换次数

1864. 构成交替字符串需要的最小交换次数

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻 。

示例 1：

输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：

输入：s = "1110"
输出：-1

提示：

• 1 <= s.length <= 1000
• s[i] 的值为 '0' 或 '1'

其实就是枚举可能存在的字符串，然后判断

class Solution {
public:
    int minSwaps(string s) {
        string fz1 ="0";
        string temp = s;
        sort(temp.begin(),temp.end());
        int yi = 0,ling = 0;
        for(int i =0;i<s.size();i++){
            if(s[i] == '0') ling++;
            else yi++;
        }
        if(abs(yi - ling)  > 1) return -1;
        for(int i = 1;i<s.size();i++){
            fz1 += fz1[i-1] == '0' ? '1': '0';
        }
        
        int cnt = 0;
        for(int i = 0;i < fz1.size();i++){
            if(fz1[i] != s[i]) cnt++;
        }
        string f =fz1;
        sort(f.begin(),f.end());
        if(f != temp) cnt = 1e9;
        fz1 = "1";
        for(int i = 1;i<s.size();i++){
            fz1 += fz1[i-1] == '0' ? '1': '0';
        }
        int cnt2 = 0;
        for(int i = 0;i < fz1.size();i++){
            if(fz1[i] != s[i]) cnt2++;
        }
        f =fz1;
        sort(f.begin(),f.end());
        if(f != temp) cnt2 = 1e9;
        return min(cnt2,cnt)/2;
    }
};