Find the Maximum Length of a Good Subsequence I

Problem Description

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1]. Return the maximum possible length of a good subsequence of nums.

Key Insights

• A subsequence can consist of the same element repeated, but to maximize its length while adhering to the good condition, we need to manage the number of distinct elements.
• The problem can be viewed as counting how many unique elements we can include while limiting the number of transitions (changes from one number to another) to k.
• If k is 0, we can only take the longest contiguous subsequence of identical elements.
• If k is greater than 0, we can include additional distinct elements up to the count of k.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array nums, since we will iterate through the array at most a few times. Space Complexity: O(u), where u is the number of unique elements in nums, for storing counts of each unique element.

Solution

To solve this problem, we can utilize a frequency map (or hash table) to count occurrences of each number in nums. By iterating through the counts, we can determine how many distinct elements we can include in our good subsequence while ensuring that the number of transitions between different elements doesn't exceed k. The approach involves:

1. Counting the frequency of each unique number in nums.
2. If the number of unique elements is less than or equal to k + 1, we can include all of them to form a good subsequence.
3. If there are more unique elements than k + 1, we can only take k + 1 unique elements, summing their frequencies to get the maximum length of the good subsequence.

Code Solutions