1963 使字符串平衡的最小交换次数

· 2025-3-17   · 次阅读   · 字数统计: 190字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

1963. 使字符串平衡的最小交换次数

分析

可以容易想到一个贪心的思路，每次将最前面的]和最后的[交换

但是对于形如 ]*]*[*[ 的括号段来说，我们可以通过交换最前面的]和最后的[的，一次交换解决两个

统计原串中非平衡字串中左括号出现的次数即可，除 $2$ 后即为答案，对于奇数情况，多进行一次交换即可

代码实现

class Solution {
public:
    int minSwaps(string s) {
        int cnt = 0;
        for(char ch : s) {
            if(ch == '[') {
                cnt++;
            }
            else if(cnt > 0) {
                cnt--;
            }
        }
        return (cnt + 1) >> 1;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$