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[1] - odd_index[0] 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[0] == i: left_para.pop(0) continue if s[i] == ')' and len(right_para) > 0 and right_para[0] == i: right_para.pop(0) continue res.append(s[i]) return ''.join(res)