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[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)

Leave a Reply

Your email address will not be published. Required fields are marked *