#3177

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Maximum Length of a Good Subsequence II

Determine the maximum length of a good subsequence in an integer array using array scanning and hash lookup efficiently.

array hash table dynamic programming

Problem Statement

Given an integer array nums and a non-negative integer k, define a sequence seq as good if at most k indices i satisfy seq[i] != seq[i + 1]. Your task is to compute the maximum length of any good subsequence of nums by selecting elements in order while respecting this constraint.

For example, with nums = [1,2,1,1,3] and k = 2, one optimal subsequence is [1,2,1,1], achieving length 4. Return a single integer representing the maximum achievable length of a good subsequence. Constraints: 1 <= nums.length <= 5000, 1 <= nums[i] <= 10^9, 0 <= k <= min(50, nums.length).

Examples

Example 1

Input: nums = [1,2,1,1,3], k = 2

Output: 4

The maximum length subsequence is [ 1 , 2 , 1 , 1 ,3] .

Example 2

Input: nums = [1,2,3,4,5,1], k = 0

Output: 2

The maximum length subsequence is [ 1 ,2,3,4,5, 1 ] .

Constraints

1 <= nums.length <= 5 * 103
1 <= nums[i] <= 109
0 <= k <= min(50, nums.length)

Solution Approach

Remap Values to Compact Range

Map all unique values in nums to a range from 0 to n - 1 to reduce space usage and simplify hash-based tracking. This step ensures consistent indexing in arrays or hash tables without altering relative order, avoiding excessive memory for large integer values.

Dynamic Programming with Hash Lookup

Use a hash table to track the maximum length of good subsequences ending with each number for every allowed change count up to k. Scan nums sequentially and update the hash table, considering whether adding the current element increments a change or continues an existing streak.

Enforce k-Change Constraint During Scanning

When extending subsequences, increment a counter only if the next element differs from the last in the current subsequence. Skip extensions that would exceed k changes. After scanning, the maximum value in the hash table represents the answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of unique elements times k for DP updates, roughly O(n * min(n,k)), while space complexity is dominated by the hash table storing lengths for each unique value and allowed change count.

What Interviewers Usually Probe

Ask about using hash tables to efficiently track subsequence lengths and transitions.
Probe understanding of remapping large integer ranges to minimize memory and simplify DP indexing.
Expect clear explanation of how k-change constraint affects subsequence extension decisions.

Common Pitfalls or Variants

Common pitfalls

Ignoring the at-most-k changes constraint when updating subsequences leads to overcounting.
Failing to remap large integer values may cause inefficient memory usage or indexing errors.
Updating the DP table incorrectly without considering previous subsequence states can reduce accuracy.

Follow-up variants

Change the subsequence rule to exactly k changes and observe DP adjustments.
Consider sequences where changes are weighted differently, requiring a modified hash-based DP.
Compute maximum length subsequences for multiple k values simultaneously for optimization.

FAQ

What is a good subsequence in Find the Maximum Length of a Good Subsequence II?

A good subsequence has at most k indices where consecutive elements differ. The problem asks for the maximum length achievable under this rule.

How does remapping nums help solve this problem?

Remapping reduces large integers to a compact index range, which simplifies hash table tracking and reduces memory usage during DP updates.

Can I solve this with a simple greedy approach?

Greedy alone may fail because selecting the next element without considering prior subsequence states can violate the at-most-k changes constraint.

What is the time complexity of the optimal approach?

Roughly O(n * min(n,k)) where n is the length of nums, because each element may update subsequences for each allowed change count.

Why use a hash table instead of just arrays?

A hash table efficiently handles arbitrary values after remapping and supports quick lookups for subsequences ending with each number while enforcing k changes.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][h]$ as the length of the longest good subsequence ending with $nums[i]$ and having no more than $h$ indices satisfying the condition. Initially, $f[i][h] = 1$. The answer is $\max(f[i][k])$, where $0 \le i < n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[0] * (k + 1) for _ in range(n)]
        mp = [defaultdict(int) for _ in range(k + 1)]
        g = [[0] * 3 for _ in range(k + 1)]
        ans = 0
        for i, x in enumerate(nums):
            for h in range(k + 1):
                f[i][h] = mp[h][x]
                if h:
                    if g[h - 1][0] != nums[i]:
                        f[i][h] = max(f[i][h], g[h - 1][1])
                    else:
                        f[i][h] = max(f[i][h], g[h - 1][2])
                f[i][h] += 1
                mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h])
                if g[h][0] != x:
                    if f[i][h] >= g[h][1]:
                        g[h][2] = g[h][1]
                        g[h][1] = f[i][h]
                        g[h][0] = x
                    else:
                        g[h][2] = max(g[h][2], f[i][h])
                else:
                    g[h][1] = max(g[h][1], f[i][h])
                ans = max(ans, f[i][h])
        return ans

Continue Practicing

#3176 find the maximum length of a good subsequence i #3186 maximum total damage with spell casting #3316 find maximum removals from source string