3177. Find the Maximum Length of a Good Subsequence II LeetCode Solution

In this guide, you will get 3177. Find the Maximum Length of a Good Subsequence II LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Length of a Good Subsequence II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find the Maximum Length of a Good Subsequence II solution in C++
4. Find the Maximum Length of a Good Subsequence II solution in Java
5. Find the Maximum Length of a Good Subsequence II solution in Python
6. Additional Resources

Problem Statement of Find the Maximum Length of a Good Subsequence II

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.

Example 1:

Input: nums = [1,2,1,1,3], k = 2
Output: 4
Explanation:
The maximum length subsequence is [1,2,1,1,3].

Example 2:

Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation:
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)

Complexity Analysis

• Time Complexity: O(nk)
• Space Complexity: O(nk)

3177. Find the Maximum Length of a Good Subsequence II LeetCode Solution in C++

class Solution {
 public:
  // Same as 3176. Find the Maximum Length of a Good Subsequence I
  int maximumLength(vector<int>& nums, int k) {
    // dp[count][num] := the maximum length of a good subsequence with at most
    // `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    vector<unordered_map<int, int>> dp(k + 1);
    // maxLen[count] := the maximum length of a good subsequence with `count`
    // indices where seq[i] != seq[i + 1]
    vector<int> maxLen(k + 1);

    for (const int num : nums)
      for (int count = k; count >= 0; --count) {
        // Append `num` to the subsequence.
        ++dp[count][num];
        if (count > 0)
          dp[count][num] = max(dp[count][num], maxLen[count - 1] + 1);
        maxLen[count] = max(maxLen[count], dp[count][num]);
      }

    return maxLen[k];
  }
};
/* code provided by PROGIEZ */

3177. Find the Maximum Length of a Good Subsequence II LeetCode Solution in Java

class Solution {
  // Same as 3176. Find the Maximum Length of a Good Subsequence I
  public int maximumLength(int[] nums, int k) {
    // dp[count][num] := the maximum length of a good subsequence with at most
    // `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    Map<Integer, Integer>[] dp = new HashMap[k + 1];
    // maxLen[count] := the maximum length of a good subsequence with `count`
    // indices where seq[i] != seq[i + 1]
    int[] maxLen = new int[k + 1];

    for (int i = 0; i <= k; ++i)
      dp[i] = new HashMap<>();

    for (final int num : nums)
      for (int count = k; count >= 0; --count) {
        // Append `num` to the subsequence.
        dp[count].merge(num, 1, Integer::sum);
        if (count > 0)
          dp[count].merge(num, maxLen[count - 1] + 1, Math::max);
        maxLen[count] = Math.max(maxLen[count], dp[count].get(num));
      }

    return maxLen[k];
  }
}
// code provided by PROGIEZ

3177. Find the Maximum Length of a Good Subsequence II LeetCode Solution in Python

class Solution:
  # Same as 3176. Find the Maximum Length of a Good Subsequence I
  def maximumLength(self, nums: list[int], k: int) -> int:
    # dp[count][num] := the maximum length of a good subsequence with at most
    # `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    dp = [collections.Counter() for _ in range(k + 1)]
    # maxLen[count] := the maximum length of a good subsequence with `count`
    # indices where seq[i] != seq[i + 1]
    maxLen = [0] * (k + 1)

    for num in nums:
      for count in range(k, -1, -1):
        # Append `num` to the subsequence.
        dp[count][num] += 1
        if count > 0:
          dp[count][num] = max(dp[count][num], maxLen[count - 1] + 1)
        maxLen[count] = max(maxLen[count], dp[count][num])

    return maxLen[k]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.