# LC 2831. Find the Longest Equal Subarray

### [Problem link](https://leetcode.com/problems/find-the-longest-equal-subarray/)

###### tags: `leedcode` `python` `c++` `medium` `Sliding Window`

You are given a **0-indexed** integer array <code>nums</code> and an integer <code>k</code>.

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** <code>k</code> elements from <code>nums</code>.

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:**

- <code>1 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] <= nums.length</code>
- <code>0 <= k <= nums.length</code>

## Solution 1 - Sliding Window(TLE)
#### Python

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

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

        res = 1
        for val, indices in d.items():
            for left in range(len(indices)):
                right = left + 1
                while right < len(indices) and indices[right] - indices[left] + 1 - (right - left + 1) <= k:
                    res = max(res, right - left + 1)
                    right += 1

        return res

## Solution 2 - Sliding Window
#### Python

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        c = Counter()
        left = 0
        res = 0
        for right in range(n):
            c[nums[right]] += 1
            res = max(res, c[nums[right]])
            if right - left + 1 - res > k:
                c[nums[left]] -= 1
                left += 1

        return res

## Solution 3 - Sliding Window
#### C++

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> cnt;
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]].push_back(i);
        }

        int ans = 0;
        for (auto& [num, idx]: cnt) {
            int l = 0;
            for (int r = 0; r < idx.size(); r++) {
                while (idx[r] - idx[l] + 1 - (r - l + 1) > k) {
                    l++;
                }
                ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(n) |
>| Solution 2 | O(n) | O(n) |
>| Solution 3 | O(n) | O(n) |

## Note
sol1:
[官神yt解說](https://www.youtube.com/watch?v=viTxUBa_Jdo)
這種講法很容易懂, 但假設num=[1,1,...,1], k=nums.length, 此時Time Complexity為O($n^2$), 會TLE.

sol2:
一樣用sliding window的想法.
[詳細想法](https://leetcode.com/problems/find-the-longest-equal-subarray/solutions/3934172/java-c-python-one-pass-sliding-window-o-n/)

sol3:
這種想法我覺得比較好想
[ref: 0x3f](https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2396401/fen-zu-shuang-zhi-zhen-pythonjavacgo-by-lqqau/)