Daily Archives: June 16, 2019

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

1. Naive way O(n^2) to calculate longest subsequence

dp[i] is the longest subsequence ending with i position.

if charAt(j) <= charAt(i), then dp[i] = max(dp[i], dp[j] + 1)

2. Only cares about column i, column j, where all chartAt(j) <= charAt(i), then we update dp[i]

public static int minDeletionSize(String[] A) {
    int[] dp = new int[A[0].length()];
    Arrays.fill(dp, 1);
    int res = A[0].length();
    for (int i = 0; i < A[0].length(); i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < A.length; k++) {
                if (A[k].charAt(j) > A[k].charAt(i)) {
                    break;
                }
                if (k == A.length - 1) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        res = Math.min(res, A[0].length() - dp[i]);
    }
    return res;
}