Longest Subarray with At Most K Duplicate Pairs
Given an array A of N integers and an integer K, find the length of the longest subarray A[i...j] such that the total number of pairs of indices (p, q) satisfying i <= p < q <= j and A[p] == A[q] is at most K.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers, the elements of the array.
Output
Print a single integer, the length of the longest valid subarray. If N=0, print 0.
Constraints
1 <= N <= 200000 1 <= K <= N Elements of the array are integers between -10^9 and 10^9.
Example 1
5 1 1 2 1 3 1
4
For K=1, the longest subarray is [1, 2, 1, 3] (length 4) which has 1 duplicate pair (A[0]=A[2]=1).
Example 2
7 2 1 1 2 2 1 3 3
5
For K=2, the subarray [2, 2, 1, 3, 3] (length 5) has exactly 2 duplicate pairs.
Hints
Similar problems
- Distinct Elements in a Sliding WindowMedium
- Count Subarrays with Distinct ElementsMedium
- Count Elements with Equal NeighborsMedium
- Longest Sorted SubsegmentMedium
- Distinct Elements in Sliding WindowMedium
- Longest Substring Without RepeatsMedium
More topics: Arrays problems, Hash Map and Hashing problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 1 2 1 3 1
7 2 1 1 2 2 1 3 3