from collections import defaultdict
class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(n)
    where, n is the length of nums
    Solved algorithm theoretically in 7 mins, coding and debugging took 1hr! Something's better than nothing, keep going and you'll improve your time, good job on problem solving skills!
    NOTE: This is OVER ENGINEERING, look below the simpler solution, more performant one in real life
    '''
    def longestBalanced(self, nums: List[int]) -> int:
        even = defaultdict(int)
        odd = defaultdict(int)
        
        def add(num):
            if num%2 == 0:
                even[num] += 1
            else:
                odd[num] += 1

        def pop(num):
            if num%2 == 0:
                even[num] -= 1
                if even[num] == 0:
                    even.pop(num)
            else:
                odd[num] -= 1
                if odd[num] == 0:
                    odd.pop(num)

        for w in range(len(nums), 1, -1):
            even = defaultdict(int)
            odd = defaultdict(int)    
            
            for i in range(w):
                add(nums[i])
            
            if len(even) == len(odd):
                return w
            
            for i in range(1, len(nums)-w+1):
                pop(nums[i-1])
                add(nums[i+w-1])
                if len(even) == len(odd):
                    return w

        return 0

class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(n)
    where, n is the length of nums
    NOTE: Theoretically, both solutions have same time and space complexity, 
    but this one is much more performant in real life, and simple to code, PREFER THIS!!
    '''
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        for i in range(n):
            seen = set()
            balance = 0
            if res > n-i:
                return res
            for j in range(i, n):
                num = nums[j]
                if num not in seen:
                    balance += 1 if num%2==0 else -1
                seen.add(num)
                if balance == 0:
                    res = max(res, j-i+1)
        
        return res