Team Up!
You are managing a college coding club. During a recruitment drive, you have a list of students, each with a unique skill represented by an integer ID. You want to form the largest possible team from a contiguous group of students such that all members of the team share at most K different skills. Find the size of the largest such team.
Input
The first line contains two integers N and K, the number of students and the maximum number of distinct skills allowed in a team. The second line contains N integers, representing the skill IDs of the students in order.
Output
Print a single integer, the maximum size of a valid team.
Constraints
1 <= N <= 200000 1 <= K <= N 1 <= skill_ID <= 10^9
Example 1
7 3 1 2 1 3 2 4 1
5
The longest subarray with at most 3 distinct skills is [1, 2, 1, 3, 2, 4] (skills: 1, 2, 3, 4 - too many), [2, 1, 3, 2, 4] (skills: 1, 2, 3, 4 - too many), [1, 2, 1, 3, 2] (skills: 1, 2, 3 - valid, length 5). The longest is [1, 2, 1, 3, 2, 4] starting at index 0 with length 6. Distinct skills are {1
Example 2
5 1 1 1 2 2 1
2
The longest subarray with at most 1 distinct skill is [1, 1] or [2, 2] or [1] (length 2).
Hints
Similar problems
- Longest Subarray with At Most K Duplicate PairsMedium
- Distinct Elements in a Sliding WindowMedium
- Longest Subarray With Sum XMedium
- Find the First Unique ElementMedium
- Count Pairs with Equal ProductMedium
- Longest Substring With At Most K Distinct CharactersMedium
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()
7 3 1 2 1 3 2 4 1
5 1 1 1 2 2 1