# LeetCode — Weekly Contest (161)

https://leetcode.com/contest/weekly-contest-161

1247. Minimum Swaps to Make Strings Equal https://leetcode.com/contest/weekly-contest-161/problems/minimum-swaps-to-make-strings-equal/

```class Solution:
def minimumSwap(self, s1: str, s2: str) -> int:
""" note that the number of x in s1 is equal to the number of y in s2, vice versa. """
x1, y1 = 0, 0
for i in range(len(s1)):
if s1[i] == s2[i]:
continue
x1 = x1 + 1 if s1[i] == 'x' else x1
y1 = y1 + 1 if s1[i] == 'y' else y1
return x1 // 2 + y1 // 2 + (x1 % 2) * 2 if (x1 + y1) % 2 == 0 else -1
```

Given the length of s1 and s2 are equal, we first need to iterate over s1 and s2 to skip the characters which are already the same. Then, for the rest characters, there are 4 combinations for character “x” and “y”: “xx”, “yy”, “xy” and “yx”. Note that currently for character “x” in s1, the corresponding character in s2 must be “y”, vice versa. Thus, Xs1 = Yx2 and Ys1 = Xs2. The corresponding combination of “xx” in s1 is “yy” in s2. “xx” and “yy” just needs 1 swap to be equal. For “xy” and “yx”, they need 2 swaps. Thus, the total number of swaps is “x1//2 + y1 // 2 + x1 % 2 * 2”.

LeetCode 1248. Count Number of Nice Subarrayshttps://leetcode.com/contest/weekly-contest-161/problems/count-number-of-nice-subarrays/

Code:

Brute Force:

```class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
"""brute force"""
res = 0
for i in range(len(nums)):
odd_nums = 0
for j in range(i, len(nums)):
odd_nums += nums[j] % 2
res = res + 1 if odd_nums == k else res
if odd_nums > k:
break
return res
```

This solution got “Time Limit Exceeded”.

Sliding Window:

Wrong Code:

```class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
"""sliding window"""
i, j = 0, -1
odd_nums = 0
nice_num = 0
while i < len(nums):
if j < len(nums) - 1 and (odd_nums < k or nums[i] % 2 == 1):
j += 1
if nums[j] % 2 == 1:
odd_nums += 1
else:
if nums[i] % 2 == 1:
odd_nums -= 1
i += 1
if odd_nums == k:
nice_num += 1
return nice_num
```

For nums = [2,2,2,1,2,2,1,2,2,2] and k =2, this solution will get 7 but 16 is expected. Why it is wrong? In common cases, for sliding window problem, the steps look like: 1) extend j until the condition is satisfied; 2) shrink i until the condition is not satisfied any more; 3) back to step 1. However, for this problem, when the condition ( the nice subarray is formed) is satisfied, we cannot shrink i immediately because there can be more j which satisfy the condition for a specific i position. Also, for a specific j position, there can be more i which satisfy the condition. (Give some diagrams to demonstrate here.)

```https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419321/JavaPython-3-1-pass-Sliding-Window-O(n)-w-comment.
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
"""sliding window"""
left_most_odd = 0
low_bound = -1
nice_num = 0
for i in range(len(nums)):
k -= nums[i] % 2
left_most_odd += (nums[left_most_odd] + 1) % 2
if k == 0:
nice_num += left_most_odd - low_bound
elif k < 0:
low_bound = left_most_odd
left_most_odd += 1
while left_most_odd < len(nums) and not nums[left_most_odd] % 2: left_most_odd += 1
k = 0
nice_num += left_most_odd - low_bound

return nice_num
```
```https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419545/JavaC%2B%2B-with-picture-deque
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
"""sliding window"""
odd_index = [-1]
res = 0
for i in range(len(nums)):
if nums[i] % 2: odd_index.append(i)
if len(odd_index) > (k + 1): odd_index.pop(0)
if len(odd_index) == (k + 1): res += odd_index - odd_index
return res
```

Explain: Continiously check the number of even numbers between odd numbers. Then, the result depends on these numbers.

LeetCode(1049) Minimum Remove to Make Valid Parentheses https://leetcode.com/contest/weekly-contest-161/problems/minimum-remove-to-make-valid-parentheses/

```class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
left_para = []
right_para = []
res = []
for i in range(len(s)):
if s[i] == '(':
left_para.append(i)
elif s[i] == ')':
if len(left_para) > 0:
left_para.pop(-1)
else:
right_para.append(i)
for i in range(len(s)):
if s[i] == '(' and len(left_para) > 0 and left_para == i:
left_para.pop(0)
continue
if s[i] == ')' and len(right_para) > 0 and right_para == i:
right_para.pop(0)
continue
res.append(s[i])
return ''.join(res)
```