<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good</strong> subarrays of</em> <code>nums</code>.</p>

<p>A subarray <code>arr</code> is <strong>good</strong> if it there are <strong>at least </strong><code>k</code> pairs of indices <code>(i, j)</code> such that <code>i &lt; j</code> and <code>arr[i] == arr[j]</code>.</p>

<p>A <strong>subarray</strong> is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], k = 10
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only good subarray is the array nums itself.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,4,3,2,2,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        
        """
        for right in range(n):

            num = nums[right]
            if num in num_freq and num_freq[num] > 0:
                num_pairs_in_window += num_freq[num]  # increment the pair count each time an element is seen again

            num_freq[num] = num_freq.get(num, 0) + 1

            # Reduce the window size until we have fewer than k pairs
            while num_pairs_in_window >= k:
                num = nums[left]
                num_freq[num] -= 1
                if num_freq[num] >= 1:
                    num_pairs_in_window -= num_freq[num]  # Decrement pairs count as the left index moves
                left += 1

            # All subarrays from left to right have at most k-1 pairs
            total_subarrays_at_most_k_minus_one_pairs += (right - left + 1)
        """
        n = len(nums)

        total_subarrays = n*(n+1)//2

        total_subarrays_at_most_k_minus_one_pairs = 0

        right = 0
        left = 0

        num_freq = {}

        num_pairs_in_window = 0

        while right < n:

            num = nums[right]

            if num in num_freq.keys():
                if num_freq[num] > 0:
                    num_pairs_in_window += num_freq[num]
                num_freq[num] += 1
            else:
                num_freq[num] = 1


            # Validate Window
            while left <= right and num_pairs_in_window >= k:
                
                num = nums[left]
                
                num_freq[num] -= 1
                num_pairs_in_window -= num_freq[num]

                left += 1

            total_subarrays_at_most_k_minus_one_pairs += right - left + 1

            right += 1


        return total_subarrays - total_subarrays_at_most_k_minus_one_pairs
542