Longest Subsequence with at Most k Value Changes
Company: BNY Mellon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given an integer array `nums` and a nonnegative integer `k`, choose a subsequence with the greatest possible length subject to this rule: at most `k` adjacent pairs in the chosen subsequence have different values.
For a chosen sequence `seq`, count indices `i` from `0` through `seq.length - 2` for which `seq[i] != seq[i + 1]`. This count must be at most `k`.
Return the maximum valid subsequence length. A subsequence retains the original order but may skip elements; it need not be contiguous.
```cpp
class Solution {
public:
int maximumLength(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [4,4,2,4,2,2], k = 1
Output: 5
Explanation: Choose indices 0, 1, 2, 4, and 5 to obtain [4,4,2,2,2], which changes value once. Taking all six elements would change value three times.
```
**Example 2:**
```text
Input: nums = [9,3,9,3,9], k = 0
Output: 3
Explanation: [9,9,9] has no adjacent unequal pair. A valid subsequence with zero changes must use only one value, and no value occurs more than three times.
```
### Constraints
- `1 <= nums.length <= 5000`.
- `1 <= nums[i] <= 10^9`.
- `0 <= k <= min(50, nums.length)`.
### Clarifying Questions
- Are changes counted in the original array? No. Count adjacent unequal pairs in the selected subsequence.
- Must exactly `k` changes occur? No, any count from zero through `k` is allowed.
- Can repeated occurrences of one value be selected across skipped elements? Yes, provided the selected indices remain in order.
- How many changes does a one-element subsequence have? Zero.
### What a Strong Answer Covers
- Preserves subsequence order and counts changes between consecutive selected values.
- Handles zero allowed changes, repeated values, and values as large as `10^9`.
- Justifies the maximum length and scales to 5000 input elements.
```hint Describe a partial subsequence
Track the last selected value and the number of changes allowed. Appending the same value and appending a different value have different effects on that budget.
```
Overview: Find the longest subsequence with at most k changes between consecutive selected values. Preserve input order and handle repeated values and a zero-change budget.