Medium

题目描述

给你一个二进制字符串 s 。你可以按任何顺序执行以下两种操作任意次：

操作 1： 移除字符串 s 的第一个字符并将它添加到字符串的末尾。 操作 2： 选择字符串 s 中的任意一个字符并将该字符翻转，即如果值为 '0' ，则变成 '1' ，反之亦然。

返回使字符串 s 交替 所需的 操作 2 的最少次数。

如果字符串中不存在相邻的两个字符相等，那么该字符串是 交替 字符串。

  • 例如，字符串 "010" 和 "1010" 是交替的，而字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

提示：

  • 1 <= s.length <= 10^5
  • s[i] 是 '0' 或 '1'

解题思路

这道题需要考虑两种操作：循环移位（操作1）和翻转字符（操作2）。关键洞察是我们需要找到所有可能的循环移位中，使字符串交替所需的最少翻转次数。

核心思路：

  1. 交替字符串只有两种模式："010101..." 和 "101010..."
  2. 对于每个可能的循环移位，计算将字符串转换为这两种模式各需要多少次翻转
  3. 使用滑动窗口优化，避免重复计算

具体方法：

  • 将原字符串复制一份接在后面，形成长度为 2n 的字符串
  • 使用长度为 n 的滑动窗口，模拟所有可能的循环移位
  • 对于每个窗口位置，计算转换为两种交替模式的代价
  • 维护全局最小值

时间复杂度优化： 使用滑动窗口技术，当窗口滑动时，只需要移除左边字符的贡献，添加右边字符的贡献，将每次计算从 O(n) 降到 O(1)。

这种方法高效地处理了所有可能的循环移位，并找到了全局最优解。

代码实现

class Solution {
public:
    int minFlips(string s) {
        int n = s.length();
        string doubled = s + s;
        
        int cost1 = 0, cost2 = 0;
        
        // Calculate initial costs for the first window
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (doubled[i] == '1') cost1++;
                else cost2++;
            } else {
                if (doubled[i] == '0') cost1++;
                else cost2++;
            }
        }
        
        int result = min(cost1, cost2);
        
        // Sliding window
        for (int i = n; i < 2 * n; i++) {
            int left = i - n;
            
            // Remove contribution of the leftmost character
            if (left % 2 == 0) {
                if (doubled[left] == '1') cost1--;
                else cost2--;
            } else {
                if (doubled[left] == '0') cost1--;
                else cost2--;
            }
            
            // Add contribution of the rightmost character
            if (i % 2 == 0) {
                if (doubled[i] == '1') cost1++;
                else cost2++;
            } else {
                if (doubled[i] == '0') cost1++;
                else cost2++;
            }
            
            result = min(result, min(cost1, cost2));
        }
        
        return result;
    }
};

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        doubled = s + s
        
        cost1 = cost2 = 0
        
        # Calculate initial costs for the first window
        for i in range(n):
            if i % 2 == 0:
                if doubled[i] == '1':
                    cost1 += 1
                else:
                    cost2 += 1
            else:
                if doubled[i] == '0':
                    cost1 += 1
                else:
                    cost2 += 1
        
        result = min(cost1, cost2)
        
        # Sliding window
        for i in range(n, 2 * n):
            left = i - n
            
            # Remove contribution of the leftmost character
            if left % 2 == 0:
                if doubled[left] == '1':
                    cost1 -= 1
                else:
                    cost2 -= 1
            else:
                if doubled[left] == '0':
                    cost1 -= 1
                else:
                    cost2 -= 1
            
            # Add contribution of the rightmost character
            if i % 2 == 0:
                if doubled[i] == '1':
                    cost1 += 1
                else:
                    cost2 += 1
            else:
                if doubled[i] == '0':
                    cost1 += 1
                else:
                    cost2 += 1
            
            result = min(result, min(cost1, cost2))
        
        return result

public class Solution {
    public int MinFlips(string s) {
        int n = s.Length;
        string doubled = s + s;
        
        int cost1 = 0, cost2 = 0;
        
        // Calculate initial costs for the first window
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (doubled[i] == '1') cost1++;
                else cost2++;
            } else {
                if (doubled[i] == '0') cost1++;
                else cost2++;
            }
        }
        
        int result = Math.Min(cost1, cost2);
        
        // Sliding window
        for (int i = n; i < 2 * n; i++) {
            int left = i - n;
            
            // Remove contribution of the leftmost character
            if (left % 2 == 0) {
                if (doubled[left] == '1') cost1--;
                else cost2--;
            } else {
                if (doubled[left] == '0') cost1--;
                else cost2--;
            }
            
            // Add contribution of the rightmost character
            if (i % 2 == 0) {
                if (doubled[i] == '1') cost1++;
                else cost2++;
            } else {
                if (doubled[i] == '0') cost1++;
                else cost2++;
            }
            
            result = Math.Min(result, Math.Min(cost1, cost2));
        }
        
        return result;
    }
}

var minFlips = function(s) {
    const n = s.length;
    const doubled = s + s;
    
    let flips01 = 0; // flips needed for pattern starting with '0'
    let flips10 = 0; // flips needed for pattern starting with '1'
    
    // Calculate initial flips for first window
    for (let i = 0; i < n; i++) {
        if ((doubled[i] === '0') !== (i % 2 === 0)) {
            flips01++;
        }
        if ((doubled[i] === '1') !== (i % 2 === 0)) {
            flips10++;
        }
    }
    
    let minFlipsNeeded = Math.min(flips01, flips10);
    
    // Sliding window
    for (let i = n; i < 2 * n; i++) {
        // Add new character
        if ((doubled[i] === '0') !== (i % 2 === 0)) {
            flips01++;
        }
        if ((doubled[i] === '1') !== (i % 2 === 0)) {
            flips10++;
        }
        
        // Remove old character
        let oldIdx = i - n;
        if ((doubled[oldIdx] === '0') !== (oldIdx % 2 === 0)) {
            flips01--;
        }
        if ((doubled[oldIdx] === '1') !== (oldIdx % 2 === 0)) {
            flips10--;
        }
        
        minFlipsNeeded = Math.min(minFlipsNeeded, flips01, flips10);
    }
    
    return minFlipsNeeded;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要遍历长度为 2n 的字符串一次，每个位置的操作都是常数时间
  • 空间复杂度：创建了一个长度为 2n 的新字符串存储doubled版本

相关题目