Problem Description

You are given an integer array nums and a non-negative integer k.

A sequence is called good if it has at most k positions where consecutive elements are different. More specifically, for a sequence seq, there can be at most k indices i (where 0 ≤ i ≤ seq.length - 2) such that seq[i] != seq[i + 1].

Your task is to find the maximum possible length of a good subsequence that can be formed from nums.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example:

• If we have a sequence [1, 1, 2, 2, 3] and k = 2, this is a good sequence because there are exactly 2 positions where consecutive elements differ: between the second 1 and first 2, and between the second 2 and 3.
• If k = 0, then the good subsequence must have all elements the same (no position where consecutive elements differ).
• If k = 1, then the good subsequence can have at most one position where consecutive elements change.

The goal is to select elements from nums (maintaining their relative order) to form the longest possible subsequence that satisfies the "good" condition with the given k.

Intuition

The key insight is that we need to track two things as we build our subsequence: which element we're currently at, and how many "changes" (positions where consecutive elements differ) we've used so far.

Think of it this way: when we're deciding whether to include an element in our subsequence, we need to know:

1. What was the last element we included?
2. How many changes have we already made?

This naturally leads to a dynamic programming approach where we define our state as f[i][h] = the maximum length of a good subsequence that ends at position i and uses at most h changes.

For each position i, we look back at all previous positions j (where j < i) and consider two cases:

1. If nums[i] == nums[j]: Adding nums[i] after nums[j] doesn't create a change (consecutive elements are the same), so we can extend the subsequence ending at j without using an additional change: f[i][h] = f[j][h] + 1.

2. If nums[i] != nums[j] and we have changes left (h > 0): Adding nums[i] after nums[j] creates a change, so we need to use one of our allowed changes. We extend the subsequence that ended at j with h-1 changes: f[i][h] = f[j][h-1] + 1.

By considering all possible previous positions j and all possible numbers of changes h from 0 to k, we can build up the maximum length subsequence. The answer is the maximum value among all f[i][k] values, representing the longest good subsequence that ends at any position and uses at most k changes.

The base case is simple: any single element forms a valid subsequence of length 1 with 0 changes, so f[i][h] = 1 initially for all valid i and h.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the dynamic programming solution using a 2D array f where f[i][h] represents the maximum length of a good subsequence ending at index i with at most h changes.

Initialization:

• Create a 2D array f of size n × (k+1) where n = len(nums)
• Initialize all values to 1, since any single element forms a valid subsequence of length 1

Main Algorithm: For each position i from 0 to n-1:

• For each allowed number of changes h from 0 to k:
  • For each previous position j from 0 to i-1:
    • Check if we can extend the subsequence ending at j to include nums[i]

Transition Formula: The state transition follows these rules:

• When nums[i] == nums[j]: We can append nums[i] to the subsequence ending at j without using any additional change, so we update f[i][h] = max(f[i][h], f[j][h] + 1)

• When nums[i] != nums[j] and h > 0: We need to use one change to append nums[i] after nums[j], so we take the subsequence that ended at j with h-1 changes and extend it: f[i][h] = max(f[i][h], f[j][h-1] + 1)

Finding the Answer: After filling the DP table, the answer is the maximum value of f[i][k] for all positions i. This represents the longest good subsequence that can end at any position while using at most k changes.

Time Complexity: O(n² × k) where n is the length of the array, as we have three nested loops.

Space Complexity: O(n × k) for the DP table.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 1, 1, 3] and k = 2.

We want to find the longest subsequence with at most 2 positions where consecutive elements differ.

Initialize DP table f[i][h]:

• f has dimensions 5×3 (5 elements, k+1=3 columns for 0,1,2 changes)
• All values start at 1 (each element alone is a valid subsequence)

Initial f:
     h=0  h=1  h=2
i=0:  1    1    1
i=1:  1    1    1  
i=2:  1    1    1
i=3:  1    1    1
i=4:  1    1    1

Process each position:

i=0 (nums[0]=1): Base case, no previous elements to consider.

i=1 (nums[1]=2):

• Look at j=0 (nums[0]=1):
  • nums[1]≠nums[0] (2≠1), so we need a change
  • For h=1: f[1][1] = max(1, f[0][0]+1) = max(1, 2) = 2
  • For h=2: f[1][2] = max(1, f[0][1]+1) = max(1, 2) = 2

i=2 (nums[2]=1):

• Look at j=0 (nums[0]=1):
  • nums[2]=nums[0] (1=1), no change needed
  • For h=0,1,2: f[2][h] = max(1, f[0][h]+1) = 2
• Look at j=1 (nums[1]=2):
  • nums[2]≠nums[1] (1≠2), need a change
  • For h=1: f[2][1] = max(2, f[1][0]+1) = max(2, 2) = 2
  • For h=2: f[2][2] = max(2, f[1][1]+1) = max(2, 3) = 3

i=3 (nums[3]=1):

• Look at j=0 (nums[0]=1):
  • nums[3]=nums[0] (1=1), no change needed
  • For all h: f[3][h] = max(1, f[0][h]+1) = 2
• Look at j=1 (nums[1]=2):
  • nums[3]≠nums[1] (1≠2), need a change
  • For h=1: f[3][1] = max(2, f[1][0]+1) = 2
  • For h=2: f[3][2] = max(2, f[1][1]+1) = 3
• Look at j=2 (nums[2]=1):
  • nums[3]=nums[2] (1=1), no change needed
  • For h=0: f[3][0] = max(2, f[2][0]+1) = 3
  • For h=1: f[3][1] = max(2, f[2][1]+1) = 3
  • For h=2: f[3][2] = max(3, f[2][2]+1) = 4

i=4 (nums[4]=3):

• Look at j=0,1,2,3 and update accordingly
• Most importantly, j=3 (nums[3]=1):
  • nums[4]≠nums[3] (3≠1), need a change
  • For h=1: f[4][1] = max(1, f[3][0]+1) = 4
  • For h=2: f[4][2] = max(1, f[3][1]+1) = 4

Final DP table:

     h=0  h=1  h=2
i=0:  1    1    1
i=1:  1    2    2  
i=2:  2    2    3
i=3:  3    3    4
i=4:  1    4    4

Answer: Maximum of f[i][2] for all i = 4

The longest good subsequence is [1, 2, 1, 1] or [2, 1, 1, 3], both with length 4 and exactly 2 changes.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × k)

The code contains three nested loops:

• The outer loop iterates through all elements in nums, running n times
• The middle loop iterates through all possible values of h from 0 to k, running k + 1 times
• The inner loop iterates through all previous elements before index i, which in the worst case is i elements

For each position i, we examine all previous positions j < i for each value of h. This gives us approximately n × (k + 1) × n/2 operations, which simplifies to O(n^2 × k).

Space Complexity: O(n × k)

The space is primarily consumed by the 2D array f, which has dimensions n × (k + 1). Each cell stores a single integer value representing the maximum length of a subsequence ending at position i with exactly h differences from the pattern. The additional variables (n, ans, loop variables) use O(1) space, so the overall space complexity is O(n × k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of the Problem Constraint

A common misunderstanding is thinking that k represents the total number of different elements allowed in the subsequence, rather than the number of positions where consecutive elements differ.

Wrong interpretation:

# Counting unique elements instead of transitions
def wrong_solution(nums, k):
    unique_count = 0
    result = []
    for num in nums:
        if num not in result:
            if unique_count < k:
                result.append(num)
                unique_count += 1
        else:
            result.append(num)
    return len(result)

Correct understanding: k limits the number of "change points" between consecutive elements in the subsequence, not the variety of elements.

2. Off-by-One Error in DP State Definition

Many implementations mistakenly define dp[i][j] as "subsequence ending at i with exactly j changes" when they actually need "at most j changes."

Problematic approach:

# Only tracking exact count, missing optimal solutions
for current_idx in range(n):
    for exact_changes in range(k + 1):  # Treating as exact count
        # Missing solutions with fewer changes
        ...

Solution: Ensure the DP state allows for using fewer changes than the maximum:

# When same values, we can use the same number of changes
if current_val == prev_val:
    dp[current_idx][diff_count] = max(
        dp[current_idx][diff_count], 
        dp[prev_idx][diff_count] + 1
    )

3. Inefficient Final Answer Extraction

A subtle pitfall is only checking dp[i][k] for the final answer, potentially missing optimal solutions that use fewer than k changes.

Incomplete answer extraction:

# Only checking exactly k changes at the last position
return dp[n-1][k]

Correct approach:

max_length = 0
# Check all positions and all valid change counts
for i in range(n):
    for j in range(k + 1):
        max_length = max(max_length, dp[i][j])
return max_length

However, the provided solution correctly handles this by checking dp[current_idx][k] which already represents "at most k changes" due to the DP transitions.

4. Memory Optimization Opportunity Missed

While not incorrect, the solution uses O(n × k) space when it could potentially be optimized using rolling arrays or hash maps for sparse states.

Space-optimized alternative using dictionary:

def maximumLength(self, nums: List[int], k: int) -> int:
    n = len(nums)
    # Use dictionary to store only necessary states
    dp = {}
  
    for i in range(n):
        for changes in range(k + 1):
            dp[(i, changes)] = 1
            for j in range(i):
                if nums[i] == nums[j]:
                    dp[(i, changes)] = max(
                        dp.get((i, changes), 1),
                        dp.get((j, changes), 1) + 1
                    )
                elif changes > 0:
                    dp[(i, changes)] = max(
                        dp.get((i, changes), 1),
                        dp.get((j, changes - 1), 1) + 1
                    )
  
    return max(dp[(i, k)] for i in range(n))

This approach saves memory when k is large and the actual number of states used is sparse.