2831.find-the-longest-equal-subarray.py

#  Tag: Array, Hash Table, Binary Search, Sliding Window
#  Time: O(N)
#  Space: O(N)
#  Ref: -
#  Note: -

#  You are given a 0-indexed integer array nums and an integer k.
#  A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.
#  Return the length of the longest possible equal subarray after deleting at most k elements from nums.
#  A subarray is a contiguous, possibly empty sequence of elements within an array.
#   
#  Example 1:
#  
#  Input: nums = [1,3,2,3,1,3], k = 3
#  Output: 3
#  Explanation: It's optimal to delete the elements at index 2 and index 4.
#  After deleting them, nums becomes equal to [1, 3, 3, 3].
#  The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
#  It can be proven that no longer equal subarrays can be created.
#  
#  Example 2:
#  
#  Input: nums = [1,1,2,2,1,1], k = 2
#  Output: 4
#  Explanation: It's optimal to delete the elements at index 2 and index 3.
#  After deleting them, nums becomes equal to [1, 1, 1, 1].
#  The array itself is an equal subarray, so the answer is 4.
#  It can be proven that no longer equal subarrays can be created.
#  
#   
#  Constraints:
#  
#  1 <= nums.length <= 105
#  1 <= nums[i] <= nums.length
#  0 <= k <= nums.length
#  
#  

from collections import defaultdict
class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        counter = defaultdict(int)
        res = 0
        i = 0
        for j in range(n):
            counter[nums[j]] += 1
            res = max(res, counter[nums[j]])
            if j - i + 1 - res > k:
                counter[nums[i]] -= 1
                i += 1

        return res


from collections import defaultdict
class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        counter = defaultdict(list)

        for i in range(n):
            counter[nums[i]].append(i)

        res = 0
        for num, indexes in counter.items():
            i = 0
            count = 0
            for j in range(len(indexes)):
                count += 1
                while indexes[j] - indexes[i] + 1 - count > k:
                    count -= 1
                    i += 1

                res = max(res, count)

        return res