thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

class Solution:
    def countGoodSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        
        def find(target):
            bitSet = [[] for _ in range(32)]
            dp = [0] * n
            for right in range(n):
                boundary = -1
                for i in range(32):
                    if (target[right] >> i) & 1 == 0:
                        last = bisect_left(bitSet[i], right)
                        if last != 0:
                            boundary = max(boundary, bitSet[i][last - 1])
                
                dp[right] = boundary
                for i in range(32):
                    if (target[right] >> i) & 1:
                        bitSet[i].append(right)
            return dp

        left = find(nums)
        rightRev = find(nums[::-1])

        prevOccurrenceMap = defaultdict(lambda: -1)
        leftOccurrenceBound = [-1] * n
        for i in range(n):
            val = nums[i]
            leftOccurrenceBound[i] = prevOccurrenceMap[val]
            prevOccurrenceMap[val] = i
        
        ans = 0
        for i in range(n):
            L = max(left[i], leftOccurrenceBound[i])
            revIdx = n - 1 - i
            revBoundary = rightRev[revIdx]
            R = n - 1 - revBoundary
            ans += (i - L) * (R - i)

        return ans©leetcode

class Solution:
    def longestBalanced(self, s: str) -> int:
        def find(s):
            zeroCount = 0
            oneCount = 0
            n = len(s)
            dp = [[0, 0]]*n
            for i in range(n - 1, -1, -1):
                dp[i] = [zeroCount, oneCount]           
                if s[i] == '0':
                    zeroCount += 1
                else:
                    oneCount += 1

        
            seen = {0: -1}
            ans = 0
            diff = 0
            for i, char in enumerate(s):
                if char == '1':
                    diff += 1
                else:
                    diff -= 1

            
                if diff + 2 in seen and dp[i][1] > 0:
                    ans = max(ans, i - seen[diff + 2])

                if diff - 2 in seen and dp[i][0] > 0:
                    ans = max(ans, i - seen[diff - 2])
    
                if diff not in seen:
                    seen[diff] = i
                else:
                    ans = max(ans, i - seen[diff])

            return ans

        return max(find(s), find(s[::-1]))