Find the Maximum Length of a Good Subsequence I

• State Definition: Let dp[i][j] be the maximum length of a good subsequence that ends with the element nums[i] and has exactly j mismatches.
• Initialization:
  • Create a 2D array dp of size n x (k+1), where n is the length of nums.
  • Initialize all entries dp[i][j] to 1. This represents the base case where the subsequence consists of only the element nums[i], which has a length of 1 and 0 mismatches.
• Transitions:
  • Iterate through the array nums with index i from 0 to n-1.
  • For each i, iterate through all previous indices p from 0 to i-1.
  • For each pair (i, p), we consider extending the subsequences that ended at p with the element nums[i].
    • Case 1: nums[i] == nums[p]
      • If the current element nums[i] is the same as the previous element nums[p], no new mismatch is created.
      • We can extend any subsequence ending at p with j mismatches. The new length will be 1 + dp[p][j].
      • So, for each j from 0 to k, we update: dp[i][j] = max(dp[i][j], 1 + dp[p][j]).
    • Case 2: nums[i] != nums[p]
      • If nums[i] is different from nums[p], a new mismatch is created.
      • We can extend a subsequence ending at p that had j-1 mismatches. This is only possible if j > 0.
      • The new length will be 1 + dp[p][j-1].
      • So, for each j from 1 to k, we update: dp[i][j] = max(dp[i][j], 1 + dp[p][j-1]).
• Final Answer:
  • The problem asks for the maximum length of a good subsequence with at most k mismatches. This means we need to find the maximum value in the entire dp table, as any entry dp[i][j] represents a valid good subsequence.
  • The overall maximum length is the maximum value found in dp after all iterations.

The core idea is to build up solutions for subsequences of increasing length. For each element nums[i], we consider it as the potential end of a new, longer subsequence. We look back at all preceding elements nums[p] and see if we can append nums[i] to a subsequence ending at nums[p]. The number of mismatches j is a crucial part of our state, as it determines whether we can append nums[i] if it's different from nums[p]. By systematically building this dp table, we ensure that we have considered all possible valid subsequences.

1class Solution {2    public int maximumLength(int[] nums, int k) {3        int n = nums.length;4        // dp[i][j]: max length of a good subsequence ending at index i with j mismatches.5        int[][] dp = new int[n][k + 1];6        int maxLength = 0;7 8        for (int i = 0; i < n; i++) {9            // Initialize dp table for index i. A single element has length 1 and 0 mismatches.10            for (int j = 0; j <= k; j++) {11                dp[i][j] = 1;12            }13 14            // Iterate through all previous elements to extend their subsequences.15            for (int p = 0; p < i; p++) {16                if (nums[i] == nums[p]) {17                    // No new mismatch.18                    for (int j = 0; j <= k; j++) {19                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j]);20                    }21                } else {22                    // New mismatch is created.23                    for (int j = 1; j <= k; j++) {24                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j - 1]);25                    }26                }27            }28        }29 30        // The answer is the maximum value in the entire dp table.31        for (int i = 0; i < n; i++) {32            for (int j = 0; j <= k; j++) {33                maxLength = Math.max(maxLength, dp[i][j]);34            }35        }36        return maxLength;37    }38}

• State Definition: We use two data structures to track the state:
  1. dp[j]: A hash map for each mismatch count j. dp[j][v] stores the maximum length of a good subsequence with exactly j mismatches that ends with the value v.
  2. maxLen[j]: An array where maxLen[j] stores the maximum length of any good subsequence with j mismatches found so far, irrespective of its ending value.
• Initialization:
  • Initialize dp as an array of k+1 empty hash maps.
  • Initialize maxLen as an array of size k+1 with all zeros.
  • Initialize ans = 1 (assuming n > 0), as the minimum possible answer is 1.
• Transitions:
  • Iterate through each num in the input array nums.
  • For each num, iterate through the number of mismatches j from k down to 0. The downward iteration is crucial to prevent using information from the current num's updates in the same pass.
  • For each j, calculate the new maximum length for a subsequence ending in num:
    • len_same = 1 + dp[j].getOrDefault(num, 0): This is the length if we extend a previous subsequence that also ended in num (no new mismatch).
    • len_diff = 1 + maxLen[j-1] (if j > 0): This is the length if we extend any subsequence with j-1 mismatches (a new mismatch is formed).
  • The new length for a subsequence ending in num with j mismatches is currentMax = max(len_same, len_diff).
  • Update the state: dp[j].put(num, currentMax) and maxLen[j] = max(maxLen[j], currentMax).
• Final Answer:
  • The overall maximum length is tracked in a variable ans, which is updated in each step: ans = max(ans, currentMax). After iterating through all numbers, ans holds the result.

The key insight for optimization is that to calculate the new length for a subsequence ending in num with j mismatches, we only need two pieces of information from the state before processing num:

1. The maximum length of a subsequence ending in num with j mismatches.
2. The maximum length of any subsequence with j-1 mismatches.

By storing these two types of information and updating them as we iterate through nums, we avoid the expensive O(n) scan for every element. We use an array of hash maps, dp, to store the first piece of information, and a simple array, maxLen, for the second. This reduces the time complexity from O(n^2 * k) to O(n * k).

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maximumLength(int[] nums, int k) {6        int n = nums.length;7        if (n == 0) {8            return 0;9        }10 11        // dp[j] is a map from value to max length of a subsequence ending with that value, using j mismatches.12        Map<Integer, Integer>[] dp = new HashMap[k + 1];13        for (int j = 0; j <= k; j++) {14            dp[j] = new HashMap<>();15        }16 17        // maxLen[j] stores the max length of any subsequence with j mismatches.18        int[] maxLen = new int[k + 1];19        int ans = 1;20 21        for (int num : nums) {22            // Iterate j from k down to 0 to use results from the previous element's iteration.23            for (int j = k; j >= 0; j--) {24                // Case 1: Extend a subsequence ending with the same value `num`.25                // No new mismatch is created.26                int lenSame = 1 + dp[j].getOrDefault(num, 0);27 28                // Case 2: Extend a subsequence ending with a different value.29                // A new mismatch is created. We need to have used j-1 mismatches before.30                int lenDiff = 0;31                if (j > 0) {32                    lenDiff = 1 + maxLen[j - 1];33                }34 35                // The new max length for a subsequence ending in `num` with `j` mismatches.36                int currentMax = Math.max(lenSame, lenDiff);37                38                // Update the DP state for the current number and mismatch count.39                dp[j].put(num, currentMax);40                41                // Update the overall max length for `j` mismatches.42                maxLen[j] = Math.max(maxLen[j], currentMax);43                44                // Update the global answer.45                ans = Math.max(ans, currentMax);46            }47        }48        return ans;49    }50}