The Painter's Palettes
A renowned artist, Mr. Pixel, is preparing for his exhibition. He has a long, thin canvas represented as a 1D strip of cells, each of which can be painted with one of several available colors. He wants to paint a contiguous segment of the canvas such that the segment uses at most K different colors. He wants to find the length of the longest such segment. Your task is to help him find this maximum length.
Input
The first line contains two integers N and K. The second line contains N integers, representing the colors of the cells in the canvas strip.
Output
Print a single integer, the maximum length of a contiguous segment using at most K distinct colors.
Constraints
1 <= N <= 200000 1 <= K <= N Colors are integers from 0 to 1,000,000,000.
Example 1
5 2 1 2 1 3 2
3
The longest segment with at most 2 distinct colors is [1, 2, 1, 3] (colors 1, 2, 3) or [2, 1, 3, 2] (colors 1, 2, 3). Wait, the distinct colors in [1,2,1,3] are {1, 2, 3}, which is 3. The segments are: [1,2] (len 2, {1,2}), [2,1] (len 2, {1,2}), [1,3] (len 2, {1,3}), [3,2] (len 2, {3,2}). Segment [1
Example 2
8 3 1 1 2 2 3 3 1 1
8
The entire array uses only 3 distinct colors (1, 2, 3) and has length 8.
Hints
Similar problems
- Longest Subarray with Limited DifferenceMedium
- Minimize Maximum Difference of Elements in IntervalsHard
- Minimum Path Sum in GridMedium
- Matrix Zero Sum SubgridsMedium
- String with Most Unique CharactersMedium
- Minimize Maximum Difference in PairsMedium
More topics: Sliding Window problems, Greedy problems, Matrix and Grid problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 2 1 3 2
8 3 1 1 2 2 3 3 1 1