Longest Segment with At Most K Distinct Elements
Given an array of N integers, find the length of the longest contiguous subsegment that contains at most K distinct integers. If multiple such subsegments have the same maximum length, return the length of the one that appears first (leftmost start index).
Input
The first line contains two integers N and K. The second line contains N integers representing the array.
Output
Print a single integer: the length of the longest subsegment with at most K distinct integers.
Constraints
1 <= N <= 200000, 1 <= K <= N, 0 <= array elements <= 10^9
Example 1
8 3 1 2 1 3 2 1 2 3
8
The longest subsegment with at most 3 distinct elements is the entire array itself (1, 2, 3), with length 8.
Example 2
10 2 1 1 2 1 3 2 2 3 1 3
4
The subsegment [1, 3, 2, 2, 3] starting at index 4 has elements {1, 3, 2}, which is 3 distinct elements. The subsegment [2, 2, 3, 1, 3] starting at index 6 has elements {2, 3, 1}, which is 3 distinct elements. The subsegment [1, 1, 2, 1] starting at index 0 has elements {1, 2}, which is 2 distinct e
Hints
Similar problems
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Substring Without RepeatsMedium
- String with Most Unique CharactersMedium
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray With Sum XMedium
- Longest Subarray with At Most K Duplicate PairsMedium
More topics: 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()
8 3 1 2 1 3 2 1 2 3
10 2 1 1 2 1 3 2 2 3 1 3