本文主要是介绍leetcode - 1963. Minimum Number of Swaps to Make the String Balanced,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets ‘[’ and n / 2 closing brackets ‘]’.
A string is called balanced if and only if:
It is the empty string, or
It can be written as AB, where both A and B are balanced strings, or
It can be written as [C], where C is a balanced string.
You may swap the brackets at any two indices any number of times.
Return the minimum number of swaps to make s balanced.
Example 1:
Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".
Example 2:
Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".
Example 3:
Input: s = "[]"
Output: 0
Explanation: The string is already balanced.
Constraints:
n == s.length
2 <= n <= 10^6
n is even.
s[i] is either '[' or ']'.
The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.
Solution
Solved after hints…
Intuitive
When there’s an imbalanced ]
, use the rightest [
to swap.
Time complexity: o ( n ) o(n) o(n)
Space complexity: o ( 1 ) o(1) o(1)
Greedy
Keep track of the maximum imbalance, to solve this imbalance, we need to do (im+1)//2
swaps.
Time complexity: o ( n ) o(n) o(n)
Space complexity: o ( 1 ) o(1) o(1)
Code
Intuitive
class Solution:def minSwaps(self, s: str) -> int:open_to_swap = len(s) - 1while open_to_swap >= 0 and s[open_to_swap] == ']':open_to_swap -= 1cnter = 0res = 0i = 0while i < open_to_swap:if s[i] == '[':cnter += 1else:cnter -= 1if cnter < 0:res += 1open_to_swap -= 1while open_to_swap >= i and s[open_to_swap] == ']':open_to_swap -= 1cnter += 2i += 1return res
Greedy
class Solution:def minSwaps(self, s: str) -> int:cnter = 0max_imbalance = 0for each_c in s:if each_c == ']':cnter -= 1else:cnter += 1max_imbalance = min(max_imbalance, cnter)return (-max_imbalance + 1) // 2
这篇关于leetcode - 1963. Minimum Number of Swaps to Make the String Balanced的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!